Question

Using the extended Euclidean algorithm, find the multiplicative inverse of a. 135 mod 61 b. 7465 mod 2464 c. 42828 mod 6407

Answer 1

(a)1≡47 mod 61

(b)1≡2329 mod 2464

(c)Does not exist

Explanation:

The operation a(mod b) has an inverse if the the two integers (a,b)

are co-prime. i.e. their g.c.d is 1.

(a)Given 135 mod 61

We first reduce it to its lowest form.

135 mod 61=13 mod 61

61=13(4)+9 ==> 9=61-13(4)

13=9(1)+4 ==> 4=13-9(1)

9=4(2)+1 ==> 1=9-4(2)

4=1(4)

Next we rewrite 1 as a linear combination of 13 and 61.

1=9-4(2)

=9-(13-9(1))2

=9(3)-13(2)

=(61-13(4))(3)-13(2)

=61(3)-13(12)-13(2)

1=61(3)-13(14)

1=61(3)+13(-14)

1≡-14 mod 61≡(-14+61)mod 61

1≡47 mod 61

(b)7465 mod 2464

Reducing it to its lowest form

7465 mod 2464=73 mod 2464

2464=73(33)+55 ==>55=2464-73(33)

73= 55(1)+18 ==> 18=73-55(1)

55=18(3)+1 ==>1=55-18(3)

18=1(18)

Rewriting 1 as a linear combination of 73 and 2464.

1=55-18(3)

=2464-73(33)-(73-55(1))(3)

=2464-73(33)-73(3)+55(3)

=2464-73(36)+55(3)

=2464-73(36)+(2464-73(33))(3)

=2464-73(36)+2464(3)-73(99)

=2464(4)-73(135)

1=2464(4)+73(-135)

Therefore:

1≡-135 mod 2464

1≡(-135+2464)mod 2464

1≡2329 mod 2464

(c)42828 mod 6407

The two numbers are not co-prime. In fact their g.c.d is 43.

Therefore their inverse does not exist.

Answer 2

The multiplicative inverse of

• A) 135 mod 61 =
  `135^(-1) = 17`

• B) 7465 mod 2464 =
  `7465^(-1) = 2329`

• C) 42828 mod 6407 =
  `inverse does not exist`

Explanation:

A)

`135 = 61 * 2 + 13\\\\61 = 13 * 4 + 9\\\\13 = 9 * 1 + 4\\\\1 = 9 -4 * 2\\\\= 9 - (13-9) * 2\\\\= 3 * 9 - 13 *2\\\\= 3 * (61-13*4) - 13 * 2\\\\= 3 * 61 - 14 * 13\\\\= 3 * 61 - 14 * (135-61*2)\\\\= 31 * 61 - 14 * 135\\\\ therefore, \\\\1 = 31*61-14*135\\\\1 = -14*135\\\\1 = 17*135\\\\135^(-1) = 17`

B)

`7465 = 2464*3+73\\\\2464 = 73*33+55\\\\73 = 55*1+18\\\\55 = 18*3+1\\\\1 = 55-18*3\\\\1 = 55-(73-55)*3\\\\1 = 4*55-73*3\\\\1 = 4*(2464-73*33)-73*3\\\\1 = 4*2464-135*73\\\\1 = 4*2464-135*(7465-2464*3)\\\\1 = 4*2464-135*7465+135*2464*3\\\\1 = 2464*(4+135*3)-135*7465\\\\1 = -135*7465\\\\1 = 2329*7465\\\\7465^(-1) = 2329`

C)
`42828 = 6*6407+4386\\\\6407 = 1*4386+2021\\\\4386 = 2*2021+344\\\\2021 = 5*344+301\\\\344 = 301*1+43\\\\301 = 7*43+0`

inverse does not exist