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 =/
 A: Continue as you started: As $3 \nmid a$, we have $a \equiv \pm 1 \pmod 3$, giving 
$$ a^4 - 1 \equiv 1 - 1 = 0 \pmod 3 $$
which means $3 \mid a^4 + 1$.
For $5$, we have either $a \equiv \pm 1 \pmod 5$, giving
$$ a^4 - 1 \equiv 1 - 1 \equiv 0 \pmod 5 $$ 
or $a \equiv \pm 2 \pmod 5$,
$$ a^4 - 1 \equiv 16 - 1 = 15 \equiv 0 \pmod 5$$
and we are done.
A: 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$$
A: Let $\,\phi\,$ be Euler's Totient Function , then
$$\phi(60)=\phi(4)\phi(3)\phi(5)=2\cdot 2\cdot 4=16$$
and in fact 
$$\left(\Bbb Z/60\Bbb Z\right)^*\cong C_2\times C_2\times C_4$$
Thus, the exponent of the above group is $\,4\,$ , which means
$$a\in\left(\Bbb Z/60\Bbb Z\right)^*\implies a^4=1$$
and from here the claim follows (why?  Check $(a,30)=1$))
A: Note $\,\phi(3)=2 = \phi(4)\mid \phi(5) = \color{#c00}4,\ $ therefore,
by little Euler:  $\ (a,n)=1  \Rightarrow\ a^{\color{#c00}4} \equiv 1\pmod{n},\ \ \text{for} \ \ n\in \{3,4,5\},$
therefore   $\,\ 3,4,5\mid a^4-1\ \Rightarrow\ 3\cdot4\cdot 5\mid a^4 - 1,\ \ $ for $\, n\,$ coprime to $\,3,4,5.$
Remark: more generally see Carmichael's lamda function, $\,\lambda(m) =\,$  exponent of  $\,\Bbb Z/m^*$
A: The question is answered successfully, I would like find the number for which $a^4\equiv1\pmod n$ for all $a$ such that $(a,n)=1$
Using Carmichael Function, If $\lambda(n)=2^m$ where integer $m\ge 1$
$n$ can not have any odd prime factor with exponent $>1$ and for each prime factor $p_i,p_i-1$ must be of the form $2^{2^{r_i}}$ where integer $r_i\ge0$
$$\text{Then if }n=2^s\cdot\prod p_i=2^s\cdot (2^{2^{r_i}}+1)$$
If $s\ge 3, \lambda(n)=$lcm $(2^{2^{r_i}},2^{s-2})$ as $\lambda(2^s)=2^{s-2}$ for $s\ge3$
$\implies\lambda(n)=$lcm $(2^{s-2},2^{2^{r_1}},2^{2^{r_2}},\cdots)=$lcm$(2^{s-2},2^{2^{\text{max}(r_i)}})$
If  $\lambda(n)$ divides $4=2^2,$ $$2^{\text{max}(r_i)}\le 2 \text{ and }s-2\le 2 \implies 0\le max(r_i)\le1 \text{ and } 3\le s\le 4 $$
For the  maximum value of $n,r_1=0,r_2=1$ and $s=4$
So, the maximum value of $n$ will be $3^1\cdot5^1\cdot2^4=240$
$$\implies x^4\equiv1\pmod {240}\implies x^4\equiv1\pmod {60}\equiv1-60=-59$$
