# Thread: inverse using modulo congruence

1. ## 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

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

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

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

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

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

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

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

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

3. 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

4. Originally Posted by 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
Thank you topsquark and Soroban