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

1. ## 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?

2. 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.

3. Originally Posted by Bruno J.
$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.