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: Prove a^n - a is multiple of n

  1. May 26, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that
    a^3 - a is a multiple of 3
    a^5 - a is a multiple of 5
    Generalise … to a^n - a a multiple of n

    2. Relevant equations

    3. The attempt at a solution
    a^3 - a = a(a^2 - 1) = a(a+1)(a-1)
    thus three consecutive numbers are multiplied. if three numbers are consecutive >0, one is a multiple of three and thus the product a multiple of three

    a^5 - a = a(a^4-1) = a(a^2+1)(a^2-1) = a(a+1)(a-1)(a^2+1)
    if i put a =1 then i get 5... but?
    and how do i generalize?
    i suspect there is just a small thing i'm missing
  2. jcsd
  3. May 26, 2012 #2
    what class is this for, i can't be sure if you already have a theorem you need.
  4. May 26, 2012 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    It looks like it's true when n is odd. Not always true when n is even.

    n=4, a=3 .
  5. May 26, 2012 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Recursion. As a starter, what is an-a in the case a=1?
  6. May 26, 2012 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    It's not always true when n is odd, either. n=9, a=4.

    There is a class of numbers for which this is always true.
  7. May 26, 2012 #6
    2^{4} - 2 = 14 \equiv 2 (\mathrm{mod} \, 4)
    So, what you are proving isn't true.
  8. May 26, 2012 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That this is not true for all all integers n has already been discussed in posts #3 and #5. The problem did not say this is true for all integers. It merely said to generalize. Part of the problem is to determine how this generalizes.
  9. May 26, 2012 #8
    From what part of the problem formulation:
    did you conclude that we should find for what n it holds?
  10. May 26, 2012 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    From the last line that says "Generalise to a^n - a"
  11. May 26, 2012 #10
    So, where does it say for what n does it hold?
  12. May 26, 2012 #11
    I think the solution is connected with this. I cannot add anything further
  13. May 26, 2012 #12

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Back to the original problem:

    jaci55555, what is the binomial expansion of (a+1)^5 ?
  14. May 27, 2012 #13
    thanks dickfore, but Dh is right, it's just to figure out if there is any generalization :) thanks tho!
    It's a post-grad class where they give us random problems to set to young children in an understandable way
    (a+1)^5 = a^5 + 4a^4 + 6a^3 + 4a^2 + a^1
    so we have the a^5 and a...
    (a-1)^5 = a^5 + 4a^4 - 6a^3 + 4a^2 - a^1
    then we have the a^5 - a
    not sure what to do with this yet though
  15. May 27, 2012 #14
    That isn't the correct expansion. You probably used n=4 for some parts and n=5 then. The coefficients of all terms are messed up, except for a5, and there is a '1' missing.

  16. May 27, 2012 #15
    (a-1)^5 = a^5 - 5a^4 +10a^3 - 10a^2 + 5a -1
  17. May 27, 2012 #16
    ooh, didn't see your reply! yes, you're right, just fixed it
  18. May 27, 2012 #17
    yep! :approve:

    Now, I'm not exactly sure whether DH was hinting at this, but as I've tried it from here, you need to prove

    [itex]a^{n} \equiv a (mod \ n)[/itex]

    For some 'special' integer n.

    Now, since you know this holds for a=1 n=1, try using induction and see if it leads to anything. Start by supposing

    [itex]a^n \equiv a (mod \ n)[/itex]

    Now you need to prove that

    [itex](a+1)^n \equiv (a+1) (mod \ n)[/itex]

    Use the binomial theorem, and separate the parts you need. You'll see the other terms can always be divided by n(for a special kind of n), once you expand it out.

    PS : Dickfore's link might give you an idea, as it is a generalization to your question.
  19. May 27, 2012 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Dickfore's hint is not appropriate for young children.

    I have a truly marvellous hint, but it's too large to fit in this reply box. :tongue2:
  20. May 27, 2012 #19


    User Avatar
    Homework Helper

    Hey, you stole my line! :rofl:

    Actually, that should be "too LITTLE to fit in this reply box". :biggrin:
  21. May 27, 2012 #20

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Kids (high school kids at least) can understand recursion and the binomial theorem. This conjecture is obviously true for all n for a=1. So this is the starting case of the recursion. As for the recursion, expand (a+1)n-(a+1) - (an-a).
  22. May 27, 2012 #21
    my computer doesn't let me see your replies until i post something. very frustrating
  23. May 27, 2012 #22

    :!!) Fermat(and DH)!

    That maybe true, but I am in high school, still. :cry: Waiting to see what an easier hint would be!

    Edit :
    Aha! I'll try messing about with this.
  24. May 27, 2012 #23
    before i can suppose this, i need to prove it true for a^5 - a... which i haven't got yet

    i think it'll work for every n prime
  25. May 27, 2012 #24
    You do not necessarily need it to be proved for n=5 to suppose that statement, you just confirmation it to be true for one first case, which it is.

    But since your actual question needs a proof for n=5, try out D H's hint for n=5. Its rather simple :smile:

    And it does work for every prime. You're basically trying to prove Fermat's Little Theorem.
  26. May 27, 2012 #25
    yay, got it all! thank you for all your help everyone! i'd put up the soln but you all had it ages ago :P
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook