Proving Divisibility Using Fermat's Theorem

[bobby2k]

Homework Statement

Prove that 2^15-2^3 divides a^15-a^3 for any integer a.
Hint: 2^15-2^3 = 5*7*8*9*13

Homework Equations

fermats theorem
eulers theorem

The Attempt at a Solution

I think that the problem is equal to show that 4080 divides any number a^13-a^3, that is

a^15-a^3 = k * 5*7*8*9*13

I was thinking about using Eulers theorem on each 5,7,8,9,13

phi(5)=4
phi(7)=7
phi(8)=4
phi(9)=6
phi(13)=12But my problem is this. This works for all the prime numbers because then gcd(a^15-a^3, prime)=1

But 8 and 9 we do not have prime numbers, so in order to use Eulers theorem i must show that
gcd(a^15-a^3,8)=1 and gcd(a^15-a^3,9)=1, correct?

How do I do this?

 

[Dick]

Homework Statement

Prove that 2^15-2^3 divides a^15-a^3 for any integer a.
Hint: 2^15-2^3 = 5*7*8*9*13

Homework Equations

fermats theorem
eulers theorem

The Attempt at a Solution

I think that the problem is equal to show that 4080 divides any number a^13-a^3, that is

a^13-a^3 = k * 5*7*8*9*13

I was thinking about using Eulers theorem on each 5,7,8,9,13

phi(5)=4
phi(7)=7
phi(8)=4
phi(9)=6
phi(13)=12But my problem is this. This works for all the prime numbers because then gcd(a^13-a^3, prime)=1

But 8 and 9 we do not have prime numbers, so in order to use Eulers theorem i must show that
gcd(a^13-a^3,8)=1 and gcd(a^13-a^3,9)=1, correct?

How do I do this?

I'm not sure what you are planning on doing with those phi's. You need to show that each of the numbers 5,7,8,9,13 divides a^15-a^3 (I'm not sure why you switched to a^13-a^3 - typo I assume). Can you show ANY of those numbers divides a^15-a^3? Just using Fermat's theorem will let you prove some of them.

 

[bobby2k]

I'm not sure what you are planning on doing with those phi's. You need to show that each of the numbers 5,7,8,9,13 divides a^15-a^3 (I'm not sure why you switched to a^13-a^3 - typo I assume). Can you show ANY of those numbers divides a^15-a^3?

Hey
Sorry it was a typo yes. I am able to show it easy for the prime numbers. Like seven for example:
Eulers theorem gives that
a^15=a^7*a^7*a = a*a*a=a^3 (mod 7)
So a^15-a^3 = 0 (mod 7).The problem comes in 8 and 9. Since we have that phi(8)=4.
We have that
a^15 = a^5*a^5*a^5=a*a*a=a^3(mod 8).
So a^15-a^3 = 0 (mod 8).

However in order for what I did to be legal for 8 and 9, I have to have that gcd(a^15-a^3, 8)=1(and the same for 9). If not, what I did in the last paragraph would not be legal.
If this is not the case, Eulers theorem can not be used, correct?

So i have to show that gcd(a^15-a^3,8)=1 and gcd(a^15-a^3,9)=1?

 

[Dick]

Hey
Sorry it was a typo yes. I am able to show it easy for the prime numbers. Like seven for example:
Eulers theorem gives that
a^15=a^7*a^7*a = a*a*a=a^3 (mod 7)
So a^15-a^3 = 0 (mod 7).The problem comes in 8 and 9. Since we have that phi(8)=4.
We have that
a^15 = a^5*a^5*a^5=a*a*a=a^3(mod 8).
So a^15-a^3 = 0 (mod 8).

However in order for what I did to be legal for 8 and 9, I have to have that gcd(a^15-a^3, 8)=1(and the same for 9). If not, what I did in the last paragraph would not be legal.
If this is not the case, Eulers theorem can not be used, correct?

So i have to show that gcd(a^15-a^3,8)=1 and gcd(a^15-a^3,9)=1?

Yes, the primes are easy. But I don't see how you can say that is legal even if gcd(a^15-a^3,8)=1, in fact, that contradicts a^15-a^3=0 (mod 8). I did 8 and 9 more directly without using either of those theorems. Take 8. If a is even then a^15-a^3 is clearly divisible by 8. If a is odd then a=2n+1 for some integer n. Can you show it's divisible by 8 in that case as well? Think about applying the binomial expansion to (2n+1)^15 and (2n+1)^3. You won't need the whole expansion, just the last few terms.

 

[bobby2k]

Yes, the primes are easy. But I don't see how you can say that is legal even if gcd(a^15-a^3,9)=1, in fact, that contradicts a^15-a^3=0 (mod 8). I did 8 and 9 more directly without using either of those theorems. Take 8. If a is even then a^15-a^3 is clearly divisible by 8. If a is odd then a=2n+1 for some integer n. Can you show it's divisible by 8 in that case as well? Think about applying the binomial expansion to (2n+1)^15 and (2n+1)^3. You won't need the whole expansion, just the last few terms.

Sorry i really screwed up. It was supposed to be that we must have that gcd(a,8), and gcd(a,9)=1, in order for that to work. But then I guess we must check what happens if they are not coprime. That is if either 2 or 3 is a factor of a, then still 8|(a^15-a^3) or 9|(a^15-a^3), but I guess we can see that this still happens.

I'll try your method, thanks!