1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 29, 2009 #1
    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|(...)


    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. jcsd
  3. Sep 29, 2009 #2


    User Avatar
    Homework Helper

    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 [itex]\Rightarrow[/itex], [itex]\Leftrightarrow[/itex] mean; please use your words instead.


    What you should have presented is:

    1. For n = 1, true.
    [tex]1 ^ 5 \equiv 1 \text{ mod} 10[/tex]
    2. Assume the statement is true for n = k, which means:
    [tex]k ^ 5 \equiv k \text{ mod} 10[/tex], or, equivalently, [tex](k ^ 5 - k) \vdots 10[/tex]
    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 [tex](k + 1) ^ 5 \equiv k + 1 \text{ mod} 10[/tex] (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. :)
  4. Sep 29, 2009 #3
    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
  5. Sep 29, 2009 #4


    User Avatar
    Science Advisor

    Often a==b(mod n) by definition means that n divides a-b. What is your definition?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook