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

elementary-number-theory

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.

Best Answer

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}. $$