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

Answer:

a. 47

b. 2329

c. These are not co-prime.

Step-by-step explanation:

a. 135 mod 61

47  

Solution is attached

b. 7465 mod 2464

2329

Solution is attached

c. 42828 mod 6407

Given n and p are not co-prime.

Answer 2

Answer:

(a)1≡47 mod 61

(b)1≡2329 mod 2464

(c)Does not exist

Step-by-step 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.