Question

With the Euclidean algorithm we finally have an efficient algorithm for finding the multiplicative inverse in Zm that is much better than exhaustive search. Find the inverses in Zm of the following elements a modulo m: 1. a=7, m=26 (affine cipher) 2. a=19, m=999

Answer 1

Answer:

a) The inverse of 7 in $Z_{26}$ is 15

b) The inverse of 19 in $Z_{999}$ is 631

Step-by-step explanation:

1)

26-3*7 = 5

7-5 = 2

5 - 2*2 = 1

Thus 1 = 5 - (2*(7-5) ) = 3 * 5 - 2*7 = 3 * (26-3*7) - 2*7 = 3*26 -11*7

Now, lets check 7 * (-11) = -77, and -63 + 3*26 = -77+78 = 1. We take as inverse -11+26 = 15 (so that it lies between 1 and 26).

2)

999/19 = 52.278....

999 - 52*19 = 11

19 - 11 = 8

11 - 8=3

8 - 2*3 = 2

3 - 2 = 1

Thus,

1 = 3-2 = 3 - (8-2*3) = 3*3-8 = 3*(11-8) - 8 = 3*11 - 4*8 = 3*11 - 4*(19-11) = 7*11-4*19 = 7*(999-52*19) - 4*19 = 7*999 - 368 * 19  

We take as inverse -368+999 = 631.

Lets check, -368*19 + 7 *999 = -6992 + 6993 = 1, it works.