Results 1 to 3 of 3

Thread: 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 $\displaystyle a$ and 30 are relatively prime, then $\displaystyle 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:

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

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

    The case breakdown I mentioned, then, is taking all the numbers $\displaystyle a$ such that $\displaystyle a$ is less than 30 and relatively prime to 30 and demonstrating that 60 divides $\displaystyle a^4+59$. Since $\displaystyle \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 $\displaystyle a^4-1$ is divisible by 60.

    It's sufficient to show that $\displaystyle 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",

    $\displaystyle a^2-1 \equiv 0 \mod 3$

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

    From the first we deduce the case for 3 because $\displaystyle 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
    $\displaystyle 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: Mar 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: Oct 11th 2011, 11:52 AM
  3. Replies: 3
    Last Post: Oct 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: Dec 24th 2010, 04:09 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum