If $\gcd(a,35)=1$ then show that $a^{12} \equiv 1 \pmod{35}$

If $\gcd(a,35)=1$, then show that $a^{12}\equiv1\pmod{35}$

I have tried this problem beginning with $a^6 \equiv 1 \pmod{7}$ and $a^4 \equiv 1 \pmod{5}$ (Fermat's Theorem) but couldn't get far enough. Please help.

Since $\gcd(a,7) =\gcd(a,5) = 1$, from Fermat's theorem,
$$a^6\equiv 1\pmod7 \quad \text{ and } \quad a^4\equiv1\pmod5. $$ Hence, $$ a^{12}\equiv 1\pmod7 \quad \text{ and } \quad a^{12}\equiv1\pmod5. $$ This means that $$7\mid a^{12}-1 \quad\text{ and } \quad 5\mid a^{12}-1. $$ Since $\gcd(7,5)=1$, $$35\mid a^{12}-1, $$ that is, $$ a^{12}\equiv1\pmod{35}. $$

One way to do this is to use Euler's totient theorem. You are familiar with Fermat's little theorem, and this is a generalized version. This approach is lengthier, but instructive, because it shows that the totient function doesn't always give you the minimal exponent. For more information, see here.

From the theorem, we know

$$a^{\phi(35)} \equiv_{35} 1$$

A simple computation shows that $\phi(35)=24$ (this can be shortened if you know more about the $\phi$ function).

So we have

$$a^{24}\equiv 1. $$

In general, if $k^2\equiv 1$, we see $(k-1)(k+1)\equiv 0$, so $k\equiv 1$ or $k\equiv -1$ (You need to think for a moment to see that other cases are ruled out, as this isn't an integral domain). Applying this to the above, we will be done once we rule out the case

$$a^{12}\equiv -1.$$

In particular, we would need $(a^6)^2$ to be $-1$ mod $35$. To show $-1$ is not a square mod $35$, it suffices to show it is not a square mod $7$ (if $a^2$ was -1 mod 35, the same $a$ mod 7 would produce $a^2\equiv -1$ mod 7).

And it is easy to see by checking all possibilities that $-1$ is not the square of any number when considered modulo 7.