Results 1 to 3 of 3

Math Help - gcd(a,30)=1 implies that 60 divides a^4+59

  1. #1
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25

    gcd(a,30)=1 implies that 60 divides a^4+59

    I'm working on this homework problem:

    Prove that if a and 30 are relatively prime, then a^4+59 is a multiple of 60.

    What I have so far is a case breakdown that seems to work, but I'm wondering if there are shortcuts I could take to reduce the number of cases or prove the result directly. Here's what I have so far:

    gcd(a,30)=gcd(a,2 \cdot 3 \cdot 5)=1 implies that 2 does not divide a, therefore gcd(a,2 \cdot 30)=gcd(a,60)=1.

    gcd(a,60)=1 can be rewritten as the Diophantine equation ax+60y=1. This, in turn, can be rewritten as ax \equiv 1(mod \ 60). I have a theorem that guarantees, for any a relatively prime to 60, exactly one solution for x.

    The case breakdown I mentioned, then, is taking all the numbers a such that a is less than 30 and relatively prime to 30 and demonstrating that 60 divides a^4+59. Since \phi(30)=8, this results in eight cases.

    Is there a better way to do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    You'll agree that it's equivalent to showing that a^4-1 is divisible by 60.

    It's sufficient to show that a^4-1 is divisible by 4, by 3 and by 5. It's easily seen to be divisible by 4 (I'll let you show that). Moreover by Fermat's "little theorem",

    a^2-1 \equiv 0 \mod 3

    a^4-1 \equiv 0 \mod 5.

    From the first we deduce the case for 3 because a^4-1=(a^2-1)(a^2+1). From the second we have the case for 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25
    Quote Originally Posted by Bruno J. View Post
    a^4-1 \equiv 0 \mod 5.
    Thanks, Bruno. One of the things I tried before was the application of Fermat's Little Theorem quoted above, but I didn't see where to go from there and thought I was on the wrong path.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. phi(n) divides n-1 implies n is prime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 6th 2012, 05:09 AM
  2. if p divides x then is xy(mod p) = 0 ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 11th 2011, 11:52 AM
  3. Replies: 3
    Last Post: October 8th 2011, 04:16 PM
  4. Replies: 2
    Last Post: May 1st 2011, 02:11 PM
  5. Proof of p implies (q implies p)
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: December 24th 2010, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum