# Problems with finding inverse by using gcd

I´ve tried to solve this problem, but i think i need some help from you guys.

In my textbook it is written that the inverse of 35 mod 3 is 2, i get that the inverse is 2, but how do you find it by using gcd? This is what i´ve done so far:

gcd(35,3)

35 = 11 * 3 + 2

3 = 1 * 2 + 1

2 = 1 * 2

1 = 3 - 1 * 2 = 3 - (35 - 11 * 3)

= -1 * 35 + 12 * 3

Shouldn´t the inverse be -1 or 12? How do i get 2?

And the same goes for the inverse of 30 mod 11. After finding the gcd, i end up with: -4 * 30 + 11 * 11. The book says that the inverse i 7, but i only get -4 and 11.

Hope someone can help me, Thanks!

• $\!\bmod 3\!:\ 35\equiv -1\,\Rightarrow\, 35^{-1}\equiv (-1)^{-1}\equiv -1\equiv 2.\,$ You don't need ext. Euclid for something that simple, but here is a much simpler form of the ext. Euclidean algorithm. – Bill Dubuque Oct 6 '18 at 18:01

You have found $$1 = -1(35)+12(3)$$

Taking modulo $$3$$.

$$1\equiv (-1)(35) \pmod{3}$$

$$-1 \pmod{3}$$ is the inverse.

Note that $$-1 \equiv 2 \pmod{3}$$.

• Thanks, i finally get it!! – Sherya Oct 6 '18 at 17:57
• But does this mean that only 2 is the inverse and not -1 and 12? – Sherya Oct 6 '18 at 22:55
• $-1$ is equivalent to $2 \pmod{3}$, hence we can say that $-1$ is an inverse as well. $12$ is not an inverse. – Siong Thye Goh Oct 7 '18 at 1:24
• You can think of one person describing $2:40$pm as $20$ minutes before $3$pm, they are equivalent. – Siong Thye Goh Oct 7 '18 at 2:53