# Homework Help: X^5 cong. x(mod10) need proof

1. Sep 29, 2009

### cap.r

1. The problem statement, all variables and given/known data
Number theory problem. we are just doing modular division and congruence theory.
x^5==x(mod10) ==> 10|x^5-x

2. Relevant equations
induction. let x=1,x=x+1

3. The attempt at a solution
let x=1 1^5==1(mod10) this is trivial but 2^5==2(mod10)...
let x=x+1
(x+1)^5==(x+1)mod10 ==> 10|(x+1)^5-(x+1)
(x+1)^5=x^5+(....)+1 ==> 10|x^5-x+(...)

now we know that 10|x^5-x by assumption. so that part is done just need to show that 10|(...)

(...)=5x^4+10x^3+10x^2+5x

obviously 10|10x^3+10x^2 so we require 10|5x^4+5x.

10|5x(x^3+1). if x is even than we can factor out a 2 and get 10|10x/2(x^3+1) and be done.
if x is odd. then x^3+1 is always even and we can factor out a 2 and get 10|10x(x^3+1)/2.

does this last part need proving? can you give me a better way of proving this? induction often works, but i like finding clever ways of doing proofs instead of brute force with induction.

2. Sep 29, 2009

### VietDao29

There are a few things you need to remember is:

• Do not start from what you need to prove. Instead, start from what you have, and from there deduce to what you need to prove.
• Unless you are positively sure about what $\Rightarrow$, $\Leftrightarrow$ mean; please use your words instead.

-----------------------

What you should have presented is:

1. For n = 1, true.
$$1 ^ 5 \equiv 1 \text{ mod} 10$$
2. Assume the statement is true for n = k, which means:
$$k ^ 5 \equiv k \text{ mod} 10$$, or, equivalently, $$(k ^ 5 - k) \vdots 10$$
3. Prove the statement is true for n = k + 1.
(k + 1)5 - (k + 1) = (k5 + 5k4 + 10k3 + 10k2 + 5k + 1) - (k + 1)
= (k5 - k) + (10k3 + 10k2) + (5k4 + 5k)

From the Induction Hypothesis, k5 - k is divisible by 10, and obviously 10k3 + 10k2 is divisible by 10.

What's left is to prove 5k4 + 5k is divisible by 10.

... (Write that part of your proof here)

Hence (k + 1)5 - (k + 1) is divisible by 10, hence $$(k + 1) ^ 5 \equiv k + 1 \text{ mod} 10$$ (Q.E.D)

---------------------------------

Another idea is to use the product of consecutive integers to prove it. The aim is to prove x5 - x is divisible by 10, for all x, right?

x5 - x = x(x4 - 1) = x(x2 - 1)(x2 + 1)
= (x - 1)x(x + 1)(x2 + 1)

Of course (x - 1)x(x + 1)(x2 + 1) is divisible by 2. (Hint: There's a product of 2 consecutive integers in that expression). So what's left is to prove that expression is also divisible by 5.

(x - 1)x(x + 1) is already a product of 3 consecutive integer. Now, let's see if you can think of a way so that the expression (x - 1)x(x + 1)(x2 + 1) can be split into the product of 5 consecutive integers. If you can then, everything is done. :)

3. Sep 29, 2009

### cap.r

so we just learned about Fermat's little theorem and it makes divisibility by 5 a trivial problem so I just used that. thank you for the help. I will do my best to make the presentation better

Last edited: Sep 29, 2009
4. Sep 29, 2009

### Landau

Often a==b(mod n) by definition means that n divides a-b. What is your definition?