What is the remainder of dividing $14^{256}$ by $17$?

Question

What is the remainder of dividing $14^{256}$ by $17$?

$$14^2\equiv 196\equiv 9 \pmod{17}\\14^{4}\equiv81\equiv13\pmod{17}\\14^8\equiv169\equiv16\pmod{17}\\14^{16}\equiv256\equiv1\pmod{17}\\14^{256}\equiv1^{16}\equiv1\pmod{17}$$

Soon rest is $1$, correct?

Answer 1

Since gcd$(14,17)=1$

Using Euler's Formula,

$$14^{\phi(17)}\equiv1\pmod{17}$$

$$14^{16}\equiv1\pmod{17}$$

but $16^2$ is $256$,

$$14^{256}\equiv1\pmod{17}$$

Answer 2

Another approach: $\;14=-3\pmod{17}\;$ , and $\,(-3)^4=3^4=13=-4\pmod{17}\;$ , so doing arithmetic modulo $\,17\,$ all through:

$$14^{256}=(-3)^{256}=\left((-3)^4\right)^{64}=(-4)^{64}=4^{64}$$

but then $\;4^2=-1\pmod {17}\;$ , so...

Answer 3

Yes, you are correct. You could also use Fermat's little theorem, which states that, if $p$ is a prime, then $$a^{p-1} \equiv 1 \pmod{p}$$ where $a$ is not a multiple of $p$. In your case, $a=14$ and $p=17$. Hence, we obtain $$14^{17-1} \equiv 1 \pmod{p} \implies 14^{16} \equiv 1 \pmod{17}$$ Now we have $$14^{256} = (14^{16})^{16} \equiv 1^{16} \pmod{17} \equiv 1 \pmod{17}$$