Solve $m \equiv 2014^{2014}\mod 17$ for the least positive value of $m$

Question

Find the least positive value of $m$ so that $m \equiv 2014^{2014}\mod 17$.

I did an euclidean algorithm between $2014$ and $17$,

$$\begin{align} 2014 &= 118 × 17 + 8\\ 17 &= 2 × 8 + 1\\ 8 &= 8 × 1 + 0 \end{align}$$

and

$$−2⋅2014+237\times17=1$$

Now using Fermat's little theorem, $17$ being a prime number, I use the form $a^{p - 1} \equiv 1 \mod p$

and further more, we know that, $2014 = 16 \times 125 + 14$

so this implies that $((2014)^{16})^{125} + 2014^{14} = 1^{125} + 2014^{14}$

Now am left to struggle with $2014^{14}$ which is still an enormously big figure. How do i go about it?

Answer 1

When you work with ${\alpha}^{\beta} \pmod a$, with $\alpha$ and $\beta$ being "big numbers", you have to reduce both.

First, let's get rid of the base $2014$.

You noticed that $2014=118\times17+8$

The value of $118$ is actually useless here, all we need is $2014 = 17\times k + 8$

From there you have: $2014 \equiv 8 \pmod {17} $

Thus, $2014^{2014} \equiv 8^{2014} \pmod {17} $

Now, you have to compute $8^{2014} \pmod {17} $, and for this:

Get rid of the exponent $2014$

To do that, you have to find a number such that $8^a \equiv \pm1 \pmod {17}$. There may be some algorithms for that, but if you have a calculator with you, trial and error can sometimes be the best way to proceed. You'll find that $8^4 \equiv -1 \pmod {17}$

Note that $2014 = 503 \times 4 + 2$

Therefore, $8^{2014} = {(8^4)}^{503}\times8^2 \equiv {(-1)}^{503} \times 64 \equiv -64 \equiv 4 \pmod {17} $

Answer 2

Your first calculation shows that $2014 \equiv 8 \pmod{17}$, so you have

$$2014^{2014} \equiv 8^{2014} \pmod{17}.$$

Your second calculation shows that $2014 \equiv 14 \pmod{16},$ so the above

$$\equiv 8^{14} \equiv 2^{42} \equiv (2^4)^{10}2^2 \equiv (-1)^{10}4 \equiv 4 \pmod{17}.$$

Answer 3

$$\begin{align} 2014^{2014} &\equiv 8^{2014} \\&\equiv 8 \cdot 8^{3^{671}} \\ &\equiv 8 \cdot 512^{671}\\ &\equiv 8 \cdot 2^{671} \\& \equiv 8 \cdot 2^{4^{167}}\cdot 2^3 \\ &\equiv 8 \cdot 16^{167}\cdot 2^3\\ &\equiv 8 \cdot (-1)^{167} \cdot 8\\ &\equiv 64 \cdot (-1)\\ &\equiv -13 \\ & \equiv 4 \mod 17 \end{align}$$