<s>[INST] Show $60 \mid (a^4+59)$ if $\gcd(a,30)=1$ 
If $\gcd(a,30)=1$ then $60 \mid (a^4+59)$.

If $\gcd(a,30)=1$ then we would be trying to show $a^4\equiv 1 \mod{60}$ or $(a^2+1)(a+1)(a-1)\equiv 0 \mod{60}$. We know $a$ must be odd and so $(a+1)$ and $(a-1)$ are even so we at least have a factor of $4$ in $a^4-1$. Was thinking I could maybe try to show that there is also a factor of $3$ and $5$ necessarily giving that $a^4-1\equiv0 \mod{60}$.
Other things I was thinking was that as $Ord_n(a) \mid \phi(n)=\phi(60)=16$ that we just need to show that $Ord_n(a) \in \{1,2,4 \}$.
Any hints? I have the exam soon =/
 [/INST] We essentially want to show that $60 \vert (a^4-1)$. Since $\gcd(a,30) = 1$, we have
$$a \equiv \pm1, \pm 7, \pm 11, \pm 13, \pm 17, \pm 19, \pm 23, \pm 29 \pmod{60}$$
Hence,
$$a^2 \equiv \begin{cases}1 \pmod{60} & \text{if }a \equiv \pm1,\pm11,\pm19,\pm29\\  -11 \pmod{60} & \text{if }a \equiv \pm7,\pm13,\pm17,\pm23\end{cases}$$
which inturn gives us
$$a^4 \equiv 1 \pmod{60} \,\,\,\, \forall a \text{ such that }\gcd(a,30) = 1$$
</s>