Scribd
Upload
2 views3 pages

Modular Multiplicative Inverses

The document provides solutions for finding the modular multiplicative inverses of several pairs of integers using the Extended Euclidean Algorithm. It includes detailed steps for calculations involving pairs (11, 12), (7, 11), (3, 7), (60, 36), and (35, 20), indicating which pairs have valid inverses and which do not. The results show that the inverses for (11, 12), (7, 11), and (3, 7) are valid, while (60, 36) and (35, 20) do not have inverses due to their gcd being greater than 1.

Uploaded by

f20221319
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Modular Multiplicative Inverses

The document provides solutions for finding the modular multiplicative inverses of several pairs of integers using the Extended Euclidean Algorithm. It includes detailed steps for calculations involving pairs (11, 12), (7, 11), (3, 7), (60, 36), and (35, 20), indicating which pairs have valid inverses and which do not. The results show that the inverses for (11, 12), (7, 11), and (3, 7) are valid, while (60, 36) and (35, 20) do not have inverses due to their gcd being greater than 1.

Uploaded by

f20221319
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Modular multiplicative inverse for 11 and 12

Solution:
y≡z-1 (modn)≡11-1 (mod12)≡11 (mod12)

Extended Euclidean Algorithm


Quotient Remainder
i t=t1-q⋅t2
q=r1÷r2 r=r1-q⋅r2 s=s1-q⋅s2
1 12 1 0
2 11 0 1
3 12÷11=1 12-1×11=1 1-1×0=1 0-1×1=-1
4 11÷1=11 11-11×1=0 0-11×1=-11 1-11×-1=12

we get answer by taking the last non-zero row for Remainder r=1 (gcd), s=1,t=-1

Here t is -ve, so add 12.

∴t=-1+12=11

∴ multiplicative inverse 11 mod 12=11

2. Modular multiplicative inverse for 7 and 11

Solution:
y≡z-1 (modn)≡7-1 (mod11)≡8 (mod11)

Extended Euclidean Algorithm


Quotient Remainder
i t=t1-q⋅t2
q=r1÷r2 r=r1-q⋅r2 s=s1-q⋅s2
1 11 1 0
2 7 0 1
3 11÷7=1 11-1×7=4 1-1×0=1 0-1×1=-1
4 7÷4=1 7-1×4=3 0-1×1=-1 1-1×-1=2
5 4÷3=1 4-1×3=1 1-1×-1=2 -1-1×2=-3
6 3÷1=3 3-3×1=0 -1-3×2=-7 2-3×-3=11

we get answer by taking the last non-zero row for Remainder r=1 (gcd), s=2,t=-3

Here t is -ve, so add 11.

∴t=-3+11=8
∴ multiplicative inverse 7 mod 11=8

3. Modular multiplicative inverse for 3 and 7

Solution:
y≡z-1 (modn)≡3-1 (mod7)≡5 (mod7)

Extended Euclidean Algorithm


Quotient Remainder
i t=t1-q⋅t2
q=r1÷r2 r=r1-q⋅r2 s=s1-q⋅s2
1 7 1 0
2 3 0 1
3 7÷3=2 7-2×3=1 1-2×0=1 0-2×1=-2
4 3÷1=3 3-3×1=0 0-3×1=-3 1-3×-2=7

we get answer by taking the last non-zero row for Remainder r=1 (gcd), s=1,t=-2

Here t is -ve, so add 7.

∴t=-2+7=5

∴ multiplicative inverse 3 mod 7=5

4. Modular multiplicative inverse for 60 and 36

Solution:
y≡z-1 (modn)≡60-1 (mod36)≡24-1 (mod36)≡0 (mod36)

Extended Euclidean Algorithm


Quotient Remainder
i t=t1-q⋅t2
q=r1÷r2 r=r1-q⋅r2 s=s1-q⋅s2
1 36 1 0
2 60 0 1
3 36÷60=0 36-0×60=36 1-0×0=1 0-0×1=0
4 60÷36=1 60-1×36=24 0-1×1=-1 1-1×0=1
5 36÷24=1 36-1×24=12 1-1×-1=2 0-1×1=-1
6 24÷12=2 24-2×12=0 -1-2×2=-5 1-2×-1=3

we get answer by taking the last non-zero row for Remainder r=12 (gcd), s=2,t=-1
Here gcd (Remainder r=12) is not 1, So 60 does not have a multiplicative inverse
modulo 36

5. Modular multiplicative inverse for 35 and 20

Solution:
y≡z-1 (modn)≡35-1 (mod20)≡15-1 (mod20)≡0 (mod20)

Extended Euclidean Algorithm


Quotient Remainder
i t=t1-q⋅t2
q=r1÷r2 r=r1-q⋅r2 s=s1-q⋅s2
1 20 1 0
2 35 0 1
3 20÷35=0 20-0×35=20 1-0×0=1 0-0×1=0
4 35÷20=1 35-1×20=15 0-1×1=-1 1-1×0=1
5 20÷15=1 20-1×15=5 1-1×-1=2 0-1×1=-1
6 15÷5=3 15-3×5=0 -1-3×2=-7 1-3×-1=4

we get answer by taking the last non-zero row for Remainder r=5 (gcd), s=2,t=-1

Here gcd (Remainder r=5) is not 1, So 35 does not have a multiplicative inverse
modulo 20

You might also like