SOLUTION: 9^563 mod907 Here is my working so far. 1) Firstly, because the power is not 2, I had to find the powers of 2 that add up to the exponent. 29 = 512 25 32 24 =16 21 =2 20

Question 1114082: 9^563 mod907

Here is my working so far.
1) Firstly, because the power is not 2, I had to find the powers of 2 that add up to the exponent.
29 = 512 25 32 24 =16 21 =2 20 1
512+32+16+2+1=563
so k =(0,1,4,5,9)
2)Calculate 92 k for 0,1,4,5,9
Where k =0 91 mod 907 = 9
ANS =9
Where k=1
81 mod 907 = 81
Where k=4
94=6561 / 907 = 7.2337
7*907 = 6349 so 6561 -6349 =212
ANS =212
95 =59049
59049/907 =65
65*907 = 58955
59049-58955=94
ANS = 94
99 =386420489 386420489 /907 =427144
427144*907=387419608
387420489-387419608=881
ANS =881
3) Multiply all the ANS together...
so...
881 x 94 x 212 x 9x 81
=158009112 mod 907
=158009112 / 907
=174210
158009112 - 158008470 = 642
ANS =642
However, the answers are:
310
520
630
493
Where have I went wrong
Answer by rothauserc(4718) (Show Source): You can put this solution on YOUR website!
9^563 mod(907)
:
2^10 = 1024 which is greater than 563 and 2^9 = 512
:
we can now decompose exponent 563 into powers of 2
:
563 = 512 + 51 = 512 + 32 + 16 + 2 + 1
:
9^563 mod(907) = 9^512+32+16+2+1 mod(907) = (9^512 * 9^32 * 9^16 * 9^2 * 9^1) mod(907)
:
now calculate the powers of 9 mod(907) - we will need
:
9^1 = 9 mod(907) = 9
9^2 = 81 mod(907) = 81
9^16 = (9^8)^2 mod(907) = 501^2 mod(907) = 251001 mod(907) = 669
9^32 = (9^16)^2 mod(907) = 669^2 mod(907) = 447561 mod(907) = 410
9^512 = (9^256)^2 mod(907) = 812^2 mod(907) = 659344 mod(907) = 862
:
to verify my calculations using this approach, you need to calculate 9^4, 9^8, 9^64, 9^128, 9^256
:
recall that
:
9^563 mod(907) = (9^512 * 9^32 * 9^16 * 9^2 * 9^1) mod(907) =
:
(862 * 410 * 669 * 81 * 9) mod(907) =
:
(353420 * 54189 * 9) mod(907) =
:
Note 862 * 410 = 353420, 669 * 81 = 54189
:
(597 * 676 * 9) mod(907) =
:
Note 353420 mod(907) = 597, 54189 mod(907) = 676
:
3632148 mod(907) =
:
520
:
********************
9^563 mod(907) = 520
********************
:

RELATED QUESTIONS
Calculate 9^563 mod907 Identify which one of the following options gives the... (answered by ikleyn,math_tutor2020)

I have been in my job for 1/4 of my life. I asked myself how long it would be until I had (answered by Alan3354)

the measure of 2 (angle 2) is 7� larger than the measure of 1. The measure of 3 is 7�... (answered by rothauserc)

I need to find the classic probability of rolling a 1 (or any number) out of 8 dice. I'm... (answered by stanbon)

I am working on a problem that I am having difficulty answering. There is not an answer... (answered by psbhowmick,richwmiller)

Find the equation of the line passing through the point (-1,-4) that is parallel to the... (answered by Alan3354)

THIS QUESTION WAS ASKED ON MY MATHS 4n + 1 = 9 I HAVE TRIED TO LOOK AT THE QUESTION IN (answered by stanbon,MathLover1)

a high school class is made up of 563 students. there are 103 more girls than boys. how... (answered by Boreal)

This question is from the Oral Exercises section. I have to state degree of each... (answered by solver91311)