# Thread: 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 $\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?

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

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

,

,

,

,

,

,

,

,

,

,

# if (a,30)=1 show that 60 divides a4 59

Click on a term to search for related topics.