SOLUTION: Calculate 9^563 mod907 Identify which one of the following options gives the correct solution for the above expression ? 310 520 630 493 My

Question 1116320: Calculate

9^563 mod907

Identify which one of the following options gives the correct solution for the above expression ?

310

520

630

493

My working:

9^563 mod 907
First I identified the exponents.
9^1 mod 907
9^2 mod 907
9^16 mod 907
9^32 mod 907
9^512 mod 907
(512+32+16+2+1=563)
9^1 mod 907=9
9^2 mod 907=81
9^16 mod 907 =669
9^32 mod 907 =410
9^512 mod 907=862
To show my working between 9^32 mod 907 and 9^512 mod 907
9^64 mod 907= 410^2 mod 907 =305
9^128 mod 907=305^2 mod 907=511
9^256 mod 907 =511^2 mod 907 = 812
9^512 mod 907= 812^2 mod 907=862
But I am not sure what is the final step....

Found 2 solutions by ikleyn, math_tutor2020:
Answer by ikleyn(52794) (Show Source): You can put this solution on YOUR website!
.
But I am not sure what is the final step....
~~~~~~~~~~~~~~~~~~~~~~~

The final steps are a) 9^563 mod907 = 8*81*669*410*862 mod907 = 153211811040 mod907. b) 153211811040/907 = 168921511.6 c) 9^563 mod907 = 153211811040 - 907*168921511 = 573. Answer. 9^563 mod907 = = 573.

I didn't check your numbers - I simply used them . . .

Answer by math_tutor2020(3817) (Show Source): You can put this solution on YOUR website!

Answer: 520

Work Shown

Let's list out the powers of 2.
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
etc...
We stop here since we won't go larger than 563.

Subtract off the largest power of 2 that is smaller than 563 or equal to it.
We'll have:
563-512 = 51
Off to the side somewhere write 512 since we'll be using it later.
Then subtract off the largest power of 2 that is smaller than 51 or equal to it.
So,
51 - 32 = 19
Write 32 off to the side to join with 512.
We keep this process going until we arrive at 0.

Here's what the scratch work looks like.
563 - 512 = 51
51 - 32 = 19
19 - 16 = 3
3 - 2 = 1
1 - 1 = 0
Those second values on the left hand side can then be reconstructed like this
1+2+16+32+512 = 563
This is useful for any time we need to convert from base 10 to binary.

It appears that you already know of this trick, but I wrote it out just in case another student is curious. The same applies for the scratch work shown in the next section.

--------------------------------------------------------------------------

Now we'll look at terms of the form 9^(2^n)
In other words we'll look at terms of the form 9^m where m is a power of 2.
Specifically we're interested in the modulus when dividing by 907.

9^1 = 9 (mod 907)
9^2 = 81 (mod 907)
are fairly straight forward.

Square both sides of the second equation to get:
9^4 = (9^2)^2 = (81)^2 = 6561 = 212 (mod 907)
Note that 6561/907 = 7 remainder 212. We ignore the quotient. The modulus only cares about the remainder.
This idea is applied many times in the scratch work shown below.

We'll repeatedly square each simplified result to generate the next term we need.

9^1 = 9 (mod 907)
9^2 = 81 (mod 907)
9^4 = (9^2)^2 = (81)^2 = 6561 = 212 (mod 907)
9^8 = (9^4)^2 = (212)^2 = 44944 = 501 (mod 907)
9^16 = (9^8)^2 = (501)^2 = 251001 = 669 (mod 907)
9^32 = (9^16)^2 = (669)^2 = 447561 = 410 (mod 907)
9^64 = (9^32)^2 = (410)^2 = 168100 = 305 (mod 907)
9^128 = (9^64)^2 = (305)^2 = 93025 = 511 (mod 907)
9^256 = (9^128)^2 = (511)^2 = 261121 = 812 (mod 907)
9^512 = (9^256)^2 = (812)^2 = 659344 = 862 (mod 907)

In short,
9^1 = 9 (mod 907)
9^2 = 81 (mod 907)
9^4 = 212 (mod 907)
9^8 = 501 (mod 907)
9^16 = 669 (mod 907)
9^32 = 410 (mod 907)
9^64 = 305 (mod 907)
9^128 = 511 (mod 907)
9^256 = 812 (mod 907)
9^512 = 862 (mod 907)

Let's toss out the rows we don't need.
We'll end up with this:
9^1 = 9 (mod 907)
9^2 = 81 (mod 907)
9^16 = 669 (mod 907)
9^32 = 410 (mod 907)
9^512 = 862 (mod 907)
Nice work on getting the correct values so far.

Then,
9^563 = 9^(1+2+16+32+512)
9^563 = (9^1)*(9^2)*(9^16)*(9^32)*(9^512)
9^563 = (9)*(81)*(669)*(410)*(862)
9^563 = (9*81)*(669*410)*(862)
9^563 = (729)*(274290)*(862)
9^563 = (729)*(376)*(862) (mod 907)
9^563 = (729*376)*(862) (mod 907)
9^563 = 274104*862 (mod 907)
9^563 = 190*862 (mod 907)
9^563 = 163780 (mod 907)
9^563 = 520 (mod 907)

You can use a tool like WolframAlpha to confirm the answer.

More practice is found here

RELATED QUESTIONS
Calculate the following in hexadecimal and identify which one of the following options... (answered by Theo)
Given Amod7=5 Bmod7=6 (A+B)mod7=Y Identify which one of... (answered by rothauserc)
Given x≡19(mod5) Identify which one of the following options gives integers... (answered by ikleyn,math_tutor2020)
9^563 mod907 Here is my working so far. 1) Firstly, because the power is not 2, I (answered by rothauserc)
Which one of the following is the correct method for evaluating the expression: 3x^2-5 (answered by checkley77)
I have the following expression: 2x^2-5 over x+9 where x=-1 so worked it to... (answered by John10)
The top of a board is resting against the side of a building, 80 cm above the ground. The (answered by lwsshak3)
For each of the following expressions, calculate the value of x which gives y a... (answered by Boreal)
Is the following series, 5 -10/3 +20/9 -40/27. Convergent, or divergent?One of the... (answered by math_tutor2020)