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

a) The inverse of 7 in is 15

b) The inverse of 19 in 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.

14 ( i believe)

Step-by-step explanation:

20 is less than 40 so we add 8+6