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

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.

• You mean $x=5^{-14}$ in ${\Bbb Z}_{17}$. – Wuestenfux Feb 6 at 16:05
• Are you allowed to use little Fermat? – Bill Dubuque Feb 6 at 16:06
• @Wuestenfux They mean the same thing since $\ a/b\,$ means $\,ab^{-1}\,$ for $\,b\,$ coprime to the modulus. – Bill Dubuque Feb 6 at 16:51
• Bill: Yes, indeed. – Wuestenfux Feb 6 at 17:31
• General hint. In problems like this you don't have to consider "large numbers" since you can reduce modulo $17$ along the way. Each of the answers takes advantage of this strategy. – Ethan Bolker Feb 6 at 23:00

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.

• I get how 5^16 is congruent to 1(mod17) but I don't understand how that help in finding the inverse. – Kayy Wang Feb 6 at 17:11
• $5^{16}=5^2 5^{14}$, so the inverse of $5^{14}$ is $5^2,$ mod 17. – J. W. Tanner Feb 6 at 17:16
• @Kayy We seek $x$ so $\,5^{\large 14} x\equiv 1.\,$ Compare that to the first congruence above (recall inverses are unique) – Bill Dubuque Feb 6 at 17:16

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

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

• $10 * 5 \equiv$ $\mathbf -1 \pmod {17}$ – J. W. Tanner Feb 6 at 23:05
• so $10^7 \equiv 5$, but in any event $10^{14} \equiv 8$, as you said – J. W. Tanner Feb 6 at 23:09