# Thread: Another modular inverse question

1. ## Another modular inverse question

Alright, so I am working a modular inverse problem. The problem is "Use the Euclidean algorithm to find the inverse of of 47 modulo 151."

So I start off with:

151 = 3 * 47 + 10
47 = 4 * 10 + 7
10 = 1 * 7 + 3
7 = 2 * 3 + 1
3 = 3 * 1 + 0

Then I rewrite so I can solve for s and t

10 = 151 - 3 * 47
7 = 47 - 4 * 10
3 = 10 - 1 * 7
1 = 7 - 2 * 3

Then I setup to find s and t

1 = 7 - 2 * 3
1 = 7 - 2 ( 10 - 1 * 7 )
1 = 7 - 2 * 10 + 2 * 7
1 = -2 * 10 + 3 * 7
1 = -2 * 10 + 3 ( 47 - 4 * 10 )
1 = -2 * 10 + 3 * 47 + 12 * 10
1 = 3 * 47 - 14 * 10
1 = 3 * 47 - 14 (151 - 3 * 47 )
1 = 3 * 47 - 14 * 151 + 42 * 47
1 = -14 * 151 + 45 * 47

s = -14
t = 45

So I found this website:
Modular inversion - Fast mod inverse calculator

And when I plug in 47 for n and 151 for p

It tells me the modular inverse is 45.

So is the modular inverse the same as t? And if not how do I solve for the modular inverse using the Euclidean Algorithm.

cheers/thanks.

2. Originally Posted by ipatch
Alright, so I am working a modular inverse problem. The problem is "Use the Euclidean algorithm to find the inverse of of 47 modulo 151."

So I start off with:

151 = 3 * 47 + 10
47 = 4 * 10 + 7
10 = 1 * 7 + 3
7 = 2 * 3 + 1
3 = 3 * 1 + 0

Then I rewrite so I can solve for s and t

10 = 151 - 3 * 47
7 = 47 - 4 * 10
3 = 10 - 1 * 7
1 = 7 - 2 * 3

Then I setup to find s and t

1 = 7 - 2 * 3
1 = 7 - 2 ( 10 - 1 * 7 )
1 = 7 - 2 * 10 + 2 * 7
1 = -2 * 10 + 3 * 7
1 = -2 * 10 + 3 ( 47 - 4 * 10 )
1 = -2 * 10 + 3 * 47 + 12 * 10
1 = 3 * 47 - 14 * 10
1 = 3 * 47 - 14 (151 - 3 * 47 )
1 = 3 * 47 - 14 * 151 + 42 * 47
1 = -14 * 151 + 45 * 47

s = -14
t = 45

So I found this website:
Modular inversion - Fast mod inverse calculator

And when I plug in 47 for n and 151 for p

It tells me the modular inverse is 45.

So is the modular inverse the same as t? And if not how do I solve for the modular inverse using the Euclidean Algorithm.

cheers/thanks.

So you got $\displaystyle 47t+151s = 1$ . Now reduce this equation $\displaystyle \pmod {151}: 47t=1\!\!\!\pmod{151}\Longrightarrow$ sure t is ALWAYS the inverse !

Tonio

3. ## Are you being facetious?

Originally Posted by tonio
So you got $\displaystyle 47t+151s = 1$ . Now reduce this equation $\displaystyle \pmod {151}: 47t=1\!\!\!\pmod{151}\Longrightarrow$ sure t is ALWAYS the inverse !

Tonio
I found another website with a modular inverse calculator

Fast Exponentation Calculator

and a website that explains how to work out the modular inverse

Chapter*3.*Modular Arithmetic

so in the example above the inverse of 15 when the modulus is 26 is going to be 7 right? 7 being the multiplicative inverse of 15 under modulus 26.

So the correct input into the calculator listed in this post for the problem
inverse of 15 modulo 26

x is 15
n is 26

yields 7