Find the multiplicative inverse of $(5^{14})$, mod $17$. Give your answer as a number in the set {$0, 1, 2,...,16$}. Do not use a calculator.

Question

Essentially $x$ = $1/(5^{14})$ mod 17. I've only used smaller numbers to find the inverse; now I'm getting confused on what to do with a larger number.

Answer 1

Hint $ $ Applying little Fermat $\ 5^{\large 14}5^{\large 2} \equiv 1\pmod{17}$

Or w/o Fermat: $\ 5^{\large 2}\!\equiv 2^{\large 3}\overset{\large (\ \ )^{\LARGE 8}}\Longrightarrow 5^{\large 16}\!\equiv (2^{\large 4})^{\large 6}\!\equiv (-1)^{\large 6}\!\equiv 1$

Or, more brute force, exponentiate by repeated squaring.

Answer 2

The inverse of $5 \pmod {17}$ is $7,$ because $5 \times 7 = 35 \equiv 1 \mod 17.$

Therefore, the inverse of $5^{14}$ is $7^{14}$.

$7^2 = 49 \equiv -2 \mod 17,$ because $17 \times 3 = 51.$

Therefore $7^4 \equiv -2 \times -2 \equiv 4 \mod 17$, and $7^8 \equiv 4 \times 4 = 16 \equiv -1 \mod 17$.

Therefore, the answer is $7^{14} = 7^2 7^4 7^8 \equiv -2 \times 4 \times -1 = 8 \mod 17.$

Answer 3

Several ways to do it. You could do $5^{14}\equiv k \pmod {17}$ and solve $k^{-1}$[1].

Or you could solve $5^{-1}= k$ and calculate $k^{14}$[2].

Or being clever you could use Fermat's Little Theorem and figure $5^{16} \equiv 1 \pmod{17}$ so $5^{-14} = 5^{16}*5^{-14}\equiv 5^{2} \pmod {17}$[3].

[3] is definitely the smartest and easiest albeit most abstract.

$5^2 = 25\equiv 8\pmod {17}$. Ta-da!

[2] Isn't hard but it is tedious.

$3*5 \equiv -2 \pmod {17}$

$(3*8)*5 \equiv -16 \pmod {17}$ so $24*5 \equiv 7*5 \equiv 1 \pmod {17}$ so $7 \equiv 5^{-1}\pmod{17}$.

So $7^2 =49 \equiv 15 \equiv -2$ and $7^4 \equiv 4$ and $7^3 \equiv -14\equiv 3$ so $7^7 \equiv 12 \equiv -5$ so $7^{14} \equiv 25 \equiv 8 \pmod {17}$.

Ta-da???

and [1].

$5^2 \equiv 25 \equiv 8$; $5^3\equiv 40 \equiv 6$; $5^4 \equiv 64 \equiv -4$. So $5^7 \equiv -24\equiv -7$ and $5^{14} \equiv 49\equiv -2$.

And $-2*8 \equiv -16\equiv 1 \pmod {17}$ so

$5^{-14}\equiv 8 \pmod {17}$.

.... Meh.....