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

Algebra ->  Sequences-and-series -> 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       Log On


   

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) About Me  (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) About Me  (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