# inverse using modulo congruence

• October 25th 2006, 06:28 AM
inverse using modulo congruence
Hi ,

Please can you help me with this problem .
I need to find the inverse of 2 modulo 11 using gcd(11,2) and modulo congruence.
I know I can start like this:

gcd(11,2)
11 = 2*5 + 1
2 = 1*2 + 0

then I used modulo congruence:

1=11 - 2*5 (mod 11)
....
I know the answer is 6 mod 11. because I used another method.
I want to know how to find it using modulo congruence.

Please can you help me ?

B
• October 25th 2006, 08:33 AM
Soroban

I don't know if this what you want, but . . .

Quote:

I need to find the inverse of 2 (mod 11)

We want to find $x$ so that: . $2x\:=\:1 \pmod{11}$

Then: . $2x - 1 \:= \:11k$ . . . for some integer $k.$

And we have: . $x \:=\:\frac{11k+1}{2}$

The 'first' value of $k$ which produces an integral $x$ is: . $k = 1$

. . which gives us: . $x = 6$

Therefore, $6$ is the multiplicative inverse of $2 \pmod{11}.$

• October 25th 2006, 08:54 AM
topsquark
Just a quick note.

The reason the inverse HAD to exist in your case is that 11 is a prime. If you were, for instance using mod 10 (a composite number), a number does not need to have an inverse, or may have more than one. You can prove these statements using Soroban's method.

-Dan
• October 25th 2006, 11:13 AM