# Homework Help: Prove a^n - a is multiple of n

1. May 26, 2012

### jaci55555

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. May 26, 2012

### algebrat

what class is this for, i can't be sure if you already have a theorem you need.

3. May 26, 2012

### SammyS

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

n=4, a=3 .

4. May 26, 2012

### D H

Staff Emeritus
Recursion. As a starter, what is an-a in the case a=1?

5. May 26, 2012

### D H

Staff Emeritus
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.

6. May 26, 2012

### Dickfore

$$2^{4} - 2 = 14 \equiv 2 (\mathrm{mod} \, 4)$$
So, what you are proving isn't true.

7. May 26, 2012

### D H

Staff Emeritus
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.

8. May 26, 2012

### Dickfore

From what part of the problem formulation:
did you conclude that we should find for what n it holds?

9. May 26, 2012

### D H

Staff Emeritus
From the last line that says "Generalise to a^n - a"

10. May 26, 2012

### Dickfore

So, where does it say for what n does it hold?

11. May 26, 2012

### Dickfore

I think the solution is connected with this. I cannot add anything further

12. May 26, 2012

### D H

Staff Emeritus
Back to the original problem:

jaci55555, what is the binomial expansion of (a+1)^5 ?

13. May 27, 2012

### jaci55555

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

14. May 27, 2012

### Infinitum

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

15. May 27, 2012

### jaci55555

no,
(a-1)^5 = a^5 - 5a^4 +10a^3 - 10a^2 + 5a -1

16. May 27, 2012

### jaci55555

17. May 27, 2012

### Infinitum

yep!

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

$a^{n} \equiv a (mod \ n)$

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

$a^n \equiv a (mod \ n)$

Now you need to prove that

$(a+1)^n \equiv (a+1) (mod \ n)$

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.

18. May 27, 2012

### D H

Staff Emeritus
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:

19. May 27, 2012

### Curious3141

Hey, you stole my line! :rofl:

Actually, that should be "too LITTLE to fit in this reply box".

20. May 27, 2012

### D H

Staff Emeritus
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).

21. May 27, 2012

### jaci55555

my computer doesn't let me see your replies until i post something. very frustrating

22. May 27, 2012

### Infinitum

:rofl:

:!!) Fermat(and DH)!

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

Edit :
Aha! I'll try messing about with this.

23. May 27, 2012

### jaci55555

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

24. May 27, 2012

### Infinitum

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

And it does work for every prime. You're basically trying to prove Fermat's Little Theorem.

25. May 27, 2012

### jaci55555

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