Prove a^n - a is multiple of n

[jaci55555]

Homework Statement

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

Homework Equations

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

 

[algebrat]

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

 

[SammyS]

Homework Statement

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

Homework Equations

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

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

n=4, a=3 .

 

[D H]

how do i generalize?
i suspect there is just a small thing I'm missing

Recursion. As a starter, what is aⁿ-a in the case a=1?

 

[D H]

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

n=4, a=3 .

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.

 

[Dickfore]

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

 

[D H]

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

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.

 

[Dickfore]

Part of the problem is to determine how this generalizes.

From what part of the problem formulation:

Homework Statement

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

did you conclude that we should find for what n it holds?

 

[D H]

From what part of the problem formulation:

Homework Statement

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

did you conclude that we should find for what n it holds?

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

 

[Dickfore]

From the last line that says "Generalise to a^n - a a multiple of n"

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

 

[Dickfore]

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

 

[D H]

Back to the original problem:

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

 

[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

 

[Infinitum]

(a+1)^5 = a^5 + 4a^4 + 6a^3 + 4a^2 + a^1

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 a⁵, and there is a '1' missing.

http://en.wikipedia.org/wiki/Binomial_theorem

 

[jaci55555]

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

 

[jaci55555]

ooh, didn't see your reply! yes, you're right, just fixed it

 

[Infinitum]

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

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.

 

[D H]

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.

 

[Curious3141]

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.

Hey, you stole my line!

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

 

[D H]

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

 

[jaci55555]

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

 

[Infinitum]

I have a truly marvellous hint, but it's too large to fit in this reply box.

:!) Fermat(and DH)!

Dickfore's hint is not appropriate for young children.

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

Edit :

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

Aha! I'll try messing about with this.

 

[jaci55555]

yep!

Start by supposing

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

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

 

[Infinitum]

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

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.

 

[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