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!

Number Theory fermats theorem

  1. Dec 2, 2013 #1
    1. The problem statement, all variables and given/known data
    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


    2. Relevant equations
    fermats theorem
    eulers theorem


    3. 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)=12


    But 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?
     
    Last edited: Dec 2, 2013
  2. jcsd
  3. Dec 2, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Dec 2, 2013
  4. Dec 2, 2013 #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?
     
  5. Dec 2, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Dec 2, 2013
  6. Dec 2, 2013 #5
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted