Proving Congruence Relations Using Division and Induction

[cap.r]

Homework Statement

Number theory problem. we are just doing modular division and congruence theory.
x^5==x(mod10) ==> 10|x^5-x

Homework Equations

induction. let x=1,x=x+1

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.

 

[VietDao29]

Homework Statement

Number theory problem. we are just doing modular division and congruence theory.
x^5==x(mod10) ==> 10|x^5-x

Homework Equations

induction. let x=1,x=x+1

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+(...)

Your idea is correct, however, your presentation is a real mess!

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)⁵ - (k + 1) = (k⁵ + 5k⁴ + 10k³ + 10k² + 5k + 1) - (k + 1)
= (k⁵ - k) + (10k³ + 10k²) + (5k⁴ + 5k)

From the Induction Hypothesis, k⁵ - k is divisible by 10, and obviously 10k³ + 10k² is divisible by 10.

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

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

Hence (k + 1)⁵ - (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 x⁵ - x is divisible by 10, for all x, right?

x⁵ - x = x(x⁴ - 1) = x(x² - 1)(x² + 1)
= (x - 1)x(x + 1)(x² + 1)

Of course (x - 1)x(x + 1)(x² + 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)(x² + 1) can be split into the product of 5 consecutive integers. If you can then, everything is done. :)

 

[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

 

[Landau]

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