Question 1116320
<font color=black size=3>
Answer: <font color=red size=4>520</font>


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 = <font color=red>520</font> (mod 907)


You can use a tool like <a href = "https://www.wolframalpha.com/input?i=9%5E563+%3D+520+%28mod+907%29">WolframAlpha</a> to confirm the answer.


More practice is found <a href = "https://www.algebra.com/algebra/homework/divisibility/lessons/successive-squaring.lesson">here</a>
</font>