35.7k views
5 votes
Using the extended euclidean algorithm, find the multiplicative inverses of
a. 13 mod 2436

1 Answer

3 votes
13 mod 2436

Step 1: Usual Euclidean algorithm

2436 = 187*13+5 ---- 1

13=2*5+3 ---- 2

5=1*3+2 ---- 3

3=1*2+1 ---- 4

Step2: Using method of back substitution

From eq 4;

1= 3-1.2

Subs eq 3

1= 3-1.(5-1.3) = 2.3-1.5

Subs eq 2

1=2.(13-2.5)-1.5

1= 2.13-4.5-1.5

1=2.13-5.5

Sub eq 1

1=2.13-5.(2436-187.13)

1=2.13-5.2436+935.13

1=937.13-5.2436

13(937)-2436(5) = 1

13 mod 2346 is 937
User Ramadhan
by
8.8k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories