# Math Help - Proof of n^5 = n mod 5 .. is this correct?

1. ## Proof of n^5 = n mod 5 .. is this correct?

I am not sure if this is a legit thing to do, so a second opinion would be nice .. also if u see any better/easier ways to do it, please let me know:

Prove that n^5 is congruent (will be denoted by =) to n mod 5

PMI
Basis: 1^5 = 1 = 1 mod 5 as needed

Inductive:
Assume k^5 = k mod n
k^5 + 1^5 = k mod 5 + 1^5 (this and the next step are the ones i question)
so k^5 + 1 ^5 = k mod 5 + 1 mod 5 (bc 1^5 is always = 1 mod 5)
So (k+1)^5 = (k+1) mod 5 as needed

is this ok?

2. Originally Posted by SKooT1027
I am not sure if this is a legit thing to do, so a second opinion would be nice .. also if u see any better/easier ways to do it, please let me know:

Prove that n^5 is congruent (will be denoted by =) to n mod 5

PMI
Basis: 1^5 = 1 = 1 mod 5 as needed

Inductive:
Assume k^5 = k mod n
k^5 + 1^5 = k mod 5 + 1^5 (this and the next step are the ones i question)
so k^5 + 1 ^5 = k mod 5 + 1 mod 5 (bc 1^5 is always = 1 mod 5)
So (k+1)^5 = (k+1) mod 5 as needed

is this ok?
No.

$k^5+1^5\neq (k+1)^5$

3. Err ok.. now that i read it, it makes it pretty obvious.. i was trying to use a proposition from my text that i didnt realize didnt hold bc of those powers

What would be a better way of going about showing n^5 = n mod 5? I assume induction isnt the best way, but it was the only thing i thought of

4. You want to prove,
$n^5-n$ is divisible by 5 (which is true this is Fermat's Little Theorem).

You can factor,
$n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)$

A number has 5 different forms,
$5k,5k+1,5k+2,5k+3,5k+4$
If $n=5k$ that is clearly true because it has a factor $n=5k$. If $n=5k+1$ that is true because it has factor $n-1=5k$. If $n=5k+4$ that is true because it has factor $n+1=5k+4=5(k+1)$. Now it remains to show that $n=5k+2,5k+3=5k\pm 2$ when squared is $5k+4$ add 1 in $n^2+1$ and you get the form of $5k$

5. Hello, SKooT1027!

Prove that $n^5 \equiv n \pmod{5}$

$S(1): \;1^5 \equiv 1 \pmod{5}$

Assume $S(k):\;k^5 \equiv k \pmod {5}$

We have: . $\begin{array}{cccccc}k^5\\ 5k^4 \\ 10k^3 \\ 10k^2 \\ 5k \\ 1\end{array}\begin{array}{cccccc}\equiv \;k \pmod{5} \\ \equiv \;0\pmod{5}\\ \equiv \;0\pmod{5}\\ \equiv\;0\pmod{5} \\ \equiv\;0\pmod{5} \\ \equiv\;1\pmod{5}\end{array}$

Add: . $k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 \;\equiv \;k + 1\pmod{5}$

Therefore: . $(k+1)^5\;\equiv\;k+1\pmod{5}$