# $n^k \equiv n \pmod 5$ for all $n\in \mathbb Z$ iff $k \equiv 1\pmod 4$

Let $k \in \mathbb N$ .Prove that $n^k \equiv n$ ( mod $5$ ) for all $n\in \mathbb Z$ iff $k \equiv 1$ ( mod $4$ )

I was trying to solve this using the corollary of Fermat's little theorem , i.e $n^p \equiv n$ ( mod $p$) for all $n \in \mathbb Z$ , but I got stuck. Need some help.

Hint: if $n$ is a multiple of $5$, so is $n^k$. If not, try showing that $n^{k-1}\equiv 1$ mod $5$ if $k\equiv 1$ mod $4$.

Edit: missed the "iff". To show that it doesn't work if $k\not\equiv 1$ mod $4$, use the if part and $n=2$. E.g. if $k\equiv 3$ mod $4$ then $2^{k-2}\equiv 2$ so $2^k\equiv 8\not\equiv 2$.

• Can you please elaborate your statement ? – Saikat Nov 6 '17 at 8:12
• @Saikat The point of a hint is to leave some of the thinking to you. Try to elaborate it yourself. – Arthur Nov 6 '17 at 8:15
• I got it. Thanks. – Saikat Nov 6 '17 at 8:29
• For the second part, the only if part, how do we know $2^{k-2} \equiv 2$? All we know is that $k-2 \equiv 1 \pmod{4}$, how did we get from there to $2^{k-2} \equiv 2 \pmod{5}$? – Max Li Nov 7 '17 at 3:00
• That's the "if" part, with $n=2$. Basically what this is saying is that the result can't be true for two values of $k$ that differ by less than $4$, so once you've proved the result is true for $k\equiv 1$ mod $4$, it can't be true for any values in between. – Especially Lime Nov 7 '17 at 8:52

First, let $k \equiv 1 (mod 4)$ then, $k=4m + 1$.
So, $n^k = n^{4m+1} = n^{4m} n$.
Now, we know, $n^4 \equiv 1 (mod 5)$ because, $1^4=1, 2^4=16, 3^4=81, 4^4=256, 6^4= 1296 ... 9^4=6561$ which are all $1 (mod 5)$[EXCEPT FOR 5, and its multiples obviously].
So, $n^4 \equiv 1 (mod 5)$ and thus $n^{4m} \equiv 1(mod 5)$.
Thus, $n^k \equiv n^{4m+1} \equiv n^{4m} n \equiv 1.n \equiv n (mod 5)$.

Similarly, you can try it out the other direction to complete the $iff$ condition.

• except n^4 congruent to 1 mod 5 is not valid when n = 5 – Derek Yin Nov 7 '17 at 5:19
• I thought it was trivial so didn't mention it. Thanks. I've edited it. – Bibekpandey Nov 7 '17 at 6:27
• not only for n=5 , n^4 congruent to 1 mod 5 is not valid when n is a multiple of 5 – Saikat Nov 8 '17 at 2:23
• Edited. Thanks. But I was actually showing the relation for last digits of any number. – Bibekpandey Nov 8 '17 at 5:06