1
$\begingroup$

This is from Discrete Mathematics and its Applications

  1. By inspection, find an inverse of 2 modulo 7

To do this, I first used Euclid's algorithm to make sure that the greatest common divisor between 2 and 7 is 1. Here is my work for that

7 = 2(3) + 1

2 = 1(2) + 0

Because 1 is the last remainder before the remainder goes to zero, it is the greatest common divisor. Because of 1 is gcd(2, 7) and m, 7, >1, by this theorem

enter image description here

the inverse of a modulo m exists. The inverse of a modulo m is in the form of

a'a $\equiv$ 1 mod(m)

in this case it be

a'*2 $\equiv$ 1 mod(7)

Where a' is the inverse

So from the steps of Euclid's algorithm

1 = (1)(7) + (-3)(2)

(-3)(2) - 1 = (1)(7)

meaning

(-3)(2) $\equiv$ 1 mod (7)

and -3 would be an inverse of 2 modulo 7. How would you find an inverse without going through the steps and just looking at it(by inspection)?

$\endgroup$
  • $\begingroup$ Look at $\frac{17+1}{2}$. You find the inverse of $2$ modulo $m$ in this way for any odd $m$. $\endgroup$ – André Nicolas Feb 13 '15 at 4:28
  • $\begingroup$ To me "by inspection" means you don't need to check obvious things like the fact that the gcd of $2$ and $7$ is $1$ ($7$ is prime, after all). The author likely meant for you to think "what number of the form $7n+1$ is a multiple of $2$?" From which you should have quickly seen $n=1$ and with $4$ as the inverse. $\endgroup$ – Hayden Feb 13 '15 at 4:29
  • $\begingroup$ @Hayden Where did 7n + 1 come from? $\endgroup$ – committedandroider Feb 13 '15 at 4:30
  • $\begingroup$ @committedandroider If $a\equiv 1 \pmod 7$, then $a=7n+1$ for some $n$. $\endgroup$ – apnorton Feb 13 '15 at 4:31
  • $\begingroup$ By inspection here just means the numbers are small enough that you can either just "see it" or you can try the small number of possibilities. For example, $2\cdot 4 = 8$, which is $1$ modulo $7$. $\endgroup$ – aes Feb 13 '15 at 4:35
3
$\begingroup$

If you want the multiplicative inverse of $2$ mod $7$, then you want to find an integer $n$ such that $2n = 7k + 1$, where $k$ is a nonnegative integer. Try $k = 1$, because that's the easiest thing to do. Then $2n= 8$, and $n = 4$.

$\endgroup$
  • $\begingroup$ Although the title mentions 17, the entirety of the question itself uses 7. (Granted, the methodology is pretty much identical) $\endgroup$ – Hayden Feb 13 '15 at 4:30
  • $\begingroup$ I changed the title, my bad. $\endgroup$ – committedandroider Feb 13 '15 at 4:31
  • $\begingroup$ Fixed the numbers. +1 $\endgroup$ – Zubin Mukerjee Feb 13 '15 at 4:36
  • $\begingroup$ So n=4, (4)(2) $\equiv$ 1(mod 7), meaning 8 - 1 is a multiple of 7. How do you guys interpret inverse? What number multiplied by a will with a difference of 1 be a multiple of m? Is that a good way to interpret inverse? I feel like there has to be a better way $\endgroup$ – committedandroider Feb 13 '15 at 5:11
  • $\begingroup$ @committedandroider A multiplicative inverse of $a$ is a number that you multiply with $a$ to give you the multiplicative identity (which is 1). When you're working with the real numbers, the inverse is $1/a$. With modulo arithmetic, you have to look for numbers congruent to $1$ and find one divisible by $a$. $\endgroup$ – NoName Feb 13 '15 at 5:30
2
$\begingroup$

You could use Euclid's algorithm to compute that gcd(2,7)=1, and from that obtain a solution to $2x+7y=1$, which in turn gives an inverse of $2$ mod $7$.

In this case, Euclid's algorithm terminates very quickly:

$7=2*3+1$

Taking this equation mod $7$ gives:

$2*3+1 \equiv 0 \pmod{7}$

$(-3)*2 \equiv 1 \pmod{7}$

So the inverse of $2$ is $-3$ which is the same as $4$.

$\endgroup$
  • $\begingroup$ How do you interpret inverse? Like if f(x) = y, f'(y) = x. That makes sense to me. Is there a way to interpret inverse in this case? $\endgroup$ – committedandroider Feb 13 '15 at 5:12
  • $\begingroup$ Inverse is in the multiplicative sense. That is, the inverse of $a$ is the element $b$ such that $ab=1$. $\endgroup$ – Dylan Yott Feb 13 '15 at 7:36
  • $\begingroup$ In that sense, -3 would be an inverse of 2 mod 7. 2 mod 7 is actually 2. -3 * 2 gives you -6, not 1. $\endgroup$ – committedandroider Feb 13 '15 at 23:26
  • $\begingroup$ $-3$ is the inverse of $2$. $4$ is also the inverse of $2$. This is okay because $-3=4$ in the ring $\mathbb Z / 7 \mathbb Z$ $\endgroup$ – Dylan Yott Feb 14 '15 at 18:13
1
$\begingroup$

If the modulus $\,m\equiv \pm1 \pmod{a},\,$ then we can easily invert $\,a\pmod m\,$ as follows

$(1)\qquad\quad {\rm mod}\,\ m = na\!-\!1\!:\ \ \ na\, \equiv 1\ \Rightarrow\ a^{-1}\equiv\,\ n \,=\, \color{#c00}{(1\!+\!m)/a}$

$(2)\qquad\quad {\rm mod}\,\ m = na\!+\!1\!:\, -na\equiv 1\:\Rightarrow\ a^{-1}\equiv -n = \color{#0a0}{(1\!-\!m)/a}$

E.g. your $\,m = 7\equiv \pm1\pmod{2},\,$ hence by $\,(2),\ \ 2^{-1} \equiv \color{#0a0}{(1\!-\!7)/2} \equiv -3$

Alternatively we can apply the case $(1)$ obtaining $\,2^{-1} \equiv \color{#c00}{(1\!+\!7)/2}\equiv\ 4$

This can be viewed as an optimization of the Extended Euclidean algorithm in the case that it terminates in a single step (or ditto for Gauss's method for modular inversion).

$\endgroup$
  • $\begingroup$ What would n be in the case of inverse of 2 modulo 7? can you show a test run of that? $\endgroup$ – committedandroider Feb 13 '15 at 5:20
  • $\begingroup$ @committedandroider Observe that $4 \cdot 2 \equiv 8 \equiv 1 \pmod{7}$, so $2^{-1} \equiv 4 \pmod{7}$. Also, observe that $3 \cdot 2 \equiv 6 \equiv -1 \pmod{7}$, so $2^{-1} \equiv -3 \equiv 4 \pmod{7}$. $\endgroup$ – N. F. Taussig Feb 13 '15 at 12:44
  • $\begingroup$ @com I explained this in an edit to the answer. $\endgroup$ – Bill Dubuque Feb 13 '15 at 19:32
0
$\begingroup$
 1 = 8 (mod 7) and 8 is a multiple of 2.

 2 x 4 = 8 = 1 mod 7

So $2^{-1} \equiv 4 \pmod 7$

Something harder. Find $5^{-1} \pmod 7$

1 = 8 = 15 mod 7 and 15 is a multiple of 5

$5 \cdot 3 = 15 = 1\pmod 7$

So $5^{-1} = 3 \pmod 7$

$\endgroup$

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.