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.