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?