1. Not finding help here? Sign up for a free 30min 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!

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

    SammyS

    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
    [tex]
    2^{4} - 2 = 14 \equiv 2 (\mathrm{mod} \, 4)
    [/tex]
    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!
    Algebrat:
    It's a post-grad class where they give us random problems to set to young children in an understandable way
    DH:
    (a+1)^5 = a^5 + 4a^4 + 6a^3 + 4a^2 + a^1
    so we have the a^5 and a...
    maybe
    (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.

    http://en.wikipedia.org/wiki/Binomial_theorem
     
  16. May 27, 2012 #15
    no,
    (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

    Curious3141

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove a^n - a is multiple of n
  1. Prove n<prime<n! (Replies: 10)

  2. Prove x^n < n! (Replies: 4)

  3. Prove n^3 <= 2^n (Replies: 9)

  4. Prove x^n<y^n (Replies: 1)

Loading...