0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ $\!\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. $\endgroup$ – Bill Dubuque Oct 6 '18 at 18:01
1
$\begingroup$

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.