3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you please elaborate your statement ? $\endgroup$ – Saikat Nov 6 '17 at 8:12
  • $\begingroup$ @Saikat The point of a hint is to leave some of the thinking to you. Try to elaborate it yourself. $\endgroup$ – Arthur Nov 6 '17 at 8:15
  • $\begingroup$ I got it. Thanks. $\endgroup$ – Saikat Nov 6 '17 at 8:29
  • $\begingroup$ 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}$? $\endgroup$ – Max Li Nov 7 '17 at 3:00
  • $\begingroup$ 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. $\endgroup$ – Especially Lime Nov 7 '17 at 8:52
-2
$\begingroup$

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.

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

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.