Question

Using the extended euclidean algorithm, find the multiplicative inverses of
a. 13 mod 2436

Answer 1

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