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

• Nov 9th 2006, 04:27 PM
SKooT1027
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?
• Nov 9th 2006, 04:34 PM
Quick
Quote:

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.

$\displaystyle k^5+1^5\neq (k+1)^5$
• Nov 9th 2006, 04:39 PM
SKooT1027
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
• Nov 9th 2006, 05:42 PM
ThePerfectHacker
You want to prove,
$\displaystyle n^5-n$ is divisible by 5 (which is true this is Fermat's Little Theorem).

You can factor,
$\displaystyle 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,
$\displaystyle 5k,5k+1,5k+2,5k+3,5k+4$
If $\displaystyle n=5k$ that is clearly true because it has a factor $\displaystyle n=5k$. If $\displaystyle n=5k+1$ that is true because it has factor $\displaystyle n-1=5k$. If $\displaystyle n=5k+4$ that is true because it has factor $\displaystyle n+1=5k+4=5(k+1)$. Now it remains to show that $\displaystyle n=5k+2,5k+3=5k\pm 2$ when squared is $\displaystyle 5k+4$ add 1 in $\displaystyle n^2+1$ and you get the form of $\displaystyle 5k$
• Nov 9th 2006, 08:24 PM
Soroban
Hello, SKooT1027!

Quote:

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

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

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

We have: .$\displaystyle \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: .$\displaystyle k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 \;\equiv \;k + 1\pmod{5}$

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