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)?
Best Answer
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$.