How to find inverse of 2 modulo 7 by inspection?
This is from Discrete Mathematics and its Applications
- 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
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$ 124 Answers
$\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$ 6 $\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$ 4 $\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$ 3 $\begingroup$ 1 = 8 (mod 7) and 8 is a multiple of 2. 2 x 4 = 8 = 1 mod 7So $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$
