0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You mean $x=5^{-14}$ in ${\Bbb Z}_{17}$. $\endgroup$ – Wuestenfux Feb 6 at 16:05
  • $\begingroup$ Are you allowed to use little Fermat? $\endgroup$ – Bill Dubuque Feb 6 at 16:06
  • $\begingroup$ @Wuestenfux They mean the same thing since $\ a/b\,$ means $\,ab^{-1}\,$ for $\,b\,$ coprime to the modulus. $\endgroup$ – Bill Dubuque Feb 6 at 16:51
  • $\begingroup$ Bill: Yes, indeed. $\endgroup$ – Wuestenfux Feb 6 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Ethan Bolker Feb 6 at 23:00
2
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.