Completely lost in this topic. I was unable to get help through any documentation (from class), and hoping if someone can help me on this.
Use exponentiation method to find each inverse. Recall ^−1 = ()^−1 .
(a) Inverse of 5 mod 17
(b) Inverse of 5 mod 21
It's using Fermat's Little Theorem to explain but I'm just lost on how to use that equation to even begin with. Can someone break this down for me?
On
Since $\gcd (5,17) = 1$ there exists some $n$ such that $5^n \equiv 1 \pmod {17}$
since 17 is prime
$5^{16} \equiv 1 \pmod {17}\\ 5^{15} \equiv 5^{-1} \pmod {17}$
There may be a $n$ smaller than 16 such that $5^{16} \equiv 1 \pmod {17}$ but we know that that will work.
However, this approach seems like a lot of work.
We can use the Euclidean algorithm to find $5m + 17n = 1$
$17 - 3\cdot 5 = 2\\ 17 - 8\cdot 2 = 1\\ (-8)\cdot (-3)\cdot 5 \equiv 1\pmod {17}\\ (24-17)\cdot 5 \equiv 1\pmod{17}$
$7 = 5^{-1}$
To use the exponentiation method, just do repeated multiplication. By Fermat's little theorem:
$5^{16} \equiv 1 \pmod {17}\\ 5^{15} \equiv 5^{-1} \pmod {17}$
But also, $5^{15} = 5\cdot 5^2\cdot5^4\cdot5^8 $. Do repeated squaring:
$5^2 \equiv 8 \pmod {17}\\ 8^2 \equiv -4 \pmod {17}\\ (-4)^2 \equiv -1 \pmod {17}$
So $5 \cdot 8 \cdot -4 \cdot -1 \equiv 7 \pmod {17}$, and therefore $5^{-1} \equiv 7\pmod {17}$