1

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)?

committedandroider
  • 1,884
  • Look at $\frac{17+1}{2}$. You find the inverse of $2$ modulo $m$ in this way for any odd $m$. – André Nicolas Feb 13 '15 at 04:28
  • 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. – Hayden Feb 13 '15 at 04:29
  • @Hayden Where did 7n + 1 come from? – committedandroider Feb 13 '15 at 04:30
  • @committedandroider If $a\equiv 1 \pmod 7$, then $a=7n+1$ for some $n$. – apnorton Feb 13 '15 at 04:31
  • 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$. – aes Feb 13 '15 at 04:35
  • @anorton ahhhh i see. Thanks – committedandroider Feb 13 '15 at 05:02
  • @AndréNicolas Where did you get (7+1)/2 from? How do you do divide in MathJax? I couldn't find it in http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – committedandroider Feb 13 '15 at 05:04
  • @Hayden did you recognize "what number of the form 7n+1 is a multiple of 2?" right away or did you do work a'2 $\equiv$ 1 (mod 7) 2a'-1 = 7k. 2a' = 7k + 1? Do you guys know how to include extra spaces in comments? – committedandroider Feb 13 '15 at 05:06
  • I had $17$ because that's what the title said. For the LaTeX, we write \frac{17+1}{2} with dollar signs at the beginning and the end. That $\frac{17+1}{2}$ gives the inverse is because when we multiply by $2$ we get $17+1$, which is congruent to $1$ modulo $17$. If $m$ is odd number $\gt 1$, the inverse of $2$ modulo $m$, for the same reason, is $\frac{m+1}{2}$. The recognition is for me instantaneous, because I have used the trick (and relatives) several times in the past. Now you too know it, and it will be instantaneous from now on. – André Nicolas Feb 13 '15 at 05:10
  • @AndréNicolas How do you interpret inverse of 2 modulo 7, which is -3, in a similar way you can interpret the inverse of a function? Say f(x) = y, then f'(y) = x. I make sense of this because the inverse takes the output and produces the original input. I can't see that type of relationship between -3 and 2 modulo 7. ? – committedandroider Feb 13 '15 at 05:18
  • You should think of it as a kind of reciprocal, like $x^{-1}$. We have $2\cdot (-3)=-6\equiv 1\pmod{7}$. (Note that modulo $7$, $-3$ and $4$ are "the same." Thinking of it as related to the inverse of a function is really not helpful. – André Nicolas Feb 13 '15 at 05:29
  • The real question is can this idea extend to 4, 8, 16 or any 2^x power inverse modulo m. As far as I can tell you basically need to resort to Euclidean methods and no shortcuts. Consider 4^(-1) mod 5. (5+1)/4 does not work as 4 is not evenly divisible so we need (5+2*5+1)/4=4. Give we always add even multiples perhaps a simplification is possible but I have yet to find one of significance. 2 is a primitive root of all odd numbers >=3 – Gregory Morse Aug 23 '21 at 01:19

4 Answers4

3

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

Zubin Mukerjee
  • 17,832
NoName
  • 2,975
  • Although the title mentions 17, the entirety of the question itself uses 7. (Granted, the methodology is pretty much identical) – Hayden Feb 13 '15 at 04:30
  • I changed the title, my bad. – committedandroider Feb 13 '15 at 04:31
  • Fixed the numbers. +1 – Zubin Mukerjee Feb 13 '15 at 04:36
  • 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 – committedandroider Feb 13 '15 at 05:11
  • @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$. – NoName Feb 13 '15 at 05:30
  • @ZachGershkoff So a'a $\equiv$ 1 mod(m). So divisible by a comes from a'a and the congruent to 1 means $\equiv$ 1? Shouldn't it be numbers congruent to 1 modulo m? – committedandroider Feb 13 '15 at 23:29
2

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

Dylan Yott
  • 6,999
1

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

Bill Dubuque
  • 272,048
0
 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$

Steven Alexis Gregory
  • 26,769