Use fast modular exponentiation to find 11 mod 115 mod 17 Th

Use fast modular exponentiation to find 11 mod 115 mod 17. The book is a bit Too clever on this. I suggest using the approach I taught in class; square repeatedly, then multiply together the terms that are needed but do as you wish.

Solution

The expression a b (mod n), pronounced “a is congruent to b modulo n,” means that a b is a multiple of n or, a – b is divisible by n. Given a, there is only one value b between 0 and n1 so that a b (mod n). We call b the residue of a modulo n and write b = (a mod n). Also A² mod C = (A * A) mod C = {(A mod C) * (A mod C)} mod C. We shall use these rules to compute the required expression.

We have 11¹ mod 17= 11mod 17 = 11

Further, 11² mod 17 = (11*11) mod 17 = {(11mod17)(11mod17)}mod 17

We can substitute our previous result for 11 mod 17 into this equation so that 11² mod 17 = (11*11)mod 17 = (11*11)mod 17 = 121 mod 17 = 2

Next, 11⁴ mod 17 = (11² *11²) mod 17 = { (11² mod 17)(11²mod17)} mod 17

We can substitute our previous result for 11² mod 17 into this equation so that 11⁴ mod 17 = (2*2) mod 17 = 4 mod17 = 4

Next 11⁸ mod 17 = (11⁴ * 11⁴ ) mod 17 = {(11⁴ mod 17)(11⁴ mod17)} mod 17

We can substitute our previous result for 11⁴ mod 17 into this equation so that 11⁸ mod 17 = (4*4) mod 17 = 16 mod17 = 16

Next 11¹⁶ mod 17 = {11⁸ mod 17)(11⁸ mod17)} mod 17

We can substitute our previous result for 11⁸ mod 17 into this equation so that 11¹⁶ mod 17 = (16*16)mod 17 = 256 mod 17 = 1

Next 11³² mod 17 = {(11¹⁶ mod 17)(11¹⁶ mod17)} mod 17

We can substitute our previous result for 11¹⁶ mod 17 into this equation so that 11³² mod 17 = ( 1*1)mod 17 = 1mod 17 = 1

Next 11⁶⁴ mod 17 = { ( 11³² mod17)(11³² mod17)}mod17

We can substitute our previous result for 11³² mod 17 into this equation so that 11⁶⁴ mod 17 = (1*1)mod 17 = 1 mod 17 = 1

Next 11⁹⁶ mod 17 = ( 11⁶⁴ * 11³²) mod 17 = { (11⁶⁴ mod 17)*( 11³² mod 17)} mod 17 . Now, we know that 11⁶⁴ mod 17 = 1 and 11³² mod 17 = 1 Therefore, 11⁹⁶ mod 17 = (1*1) mod 17 = 1mod 17 = 1.

Next 11¹¹² mod 17 = ( 11⁹⁶ * 11¹⁶ ) mod 17 = { (11⁹⁶ mod 17)(11¹⁶ mod 17)} mod 17 = (1*1)mod 17 = 1mod17 = 1

Also 11³ mod 17 = (11² * 11)mod 17 = {( 11² mod17)( 11 mod17)} mod17 = (2*11) mod 17 = 22 mod 17 = 5.

Now, finally, 11¹¹⁵ mod 17 = (11¹¹² * 11³ ) mod 17 = { (11¹¹² mod 17) ( 11³ mod 17)} mod 17 = (1* 5) mod 17 = 5 mod 17 = 5