# show that $a^{12} \equiv 1 \mod 32760$ for each $a \in \mathbb{Z}$ such that $\text{gcd}(a, 32760) = 1$

I am trying to show that $a^{12} \equiv 1 \mod 32760$ for each $a \in \mathbb{Z}$ coprime to $32760$. I have found the prime decomposition $32760 = 2^3 \cdot 3^3 \cdot 5 \cdot 7 \cdot 13$ and determined $\phi(32760)$, where $\phi$ is the Euler's totient function. This gives me that $\phi (32760) = 8640$.

Using Euler's congruence, this gives that $a^{8640} \equiv 1 \mod 32760$, but this is still far from the result I want to show... I also know a consequence of Eulers congruence, which states that $e \equiv e' \mod \phi (n)$ implies that $a^e \equiv a^{e'} \mod n$, but I do not see how to use this...

Any hints would be appreciated.

$\textbf{EDIT:}$ I made a mistake in my primefactorization, it is edited now.

• $7^{12} \neq 1 \mod 32760$
– Leox
Feb 16 '17 at 18:28
• @Leox, $\gcd(7, 32760) \ne 1$.
– lhf
Feb 16 '17 at 18:29
• Your prime factorization is incorrect. $32760 = 2^3 \cdot 3^2 \cdot 5\cdot 7\cdot 13$ Feb 16 '17 at 18:31
• @lhf yes, just his factorisation was wrong
– Leox
Feb 16 '17 at 18:36

For each maximal prime power $$\,p^{\large k}$$ dividing $$\, 32760 = 2^{\large 3} \cdot 3^{\large 2} \cdot 5\cdot 7\cdot 13\,$$ we have that Euler's $$\,\phi = \phi(p^k)\mid 12,\$$ so $$\,12 = \phi k,\,$$ so $$\ {\rm mod}\,\ p^{\large k}\!:\,\ a^{\large 12} \equiv (\color{#c00}{a^{\large \phi}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\,$$ by $$\rm\color{#c00}{Euler's}$$ Theorem.

Thus, since all $$\,p^{\large k}$$ divide $$\, a^{\large 12}\!-1,\,$$ so too does their lcm = product $$= 32760$$

Remark $$\$$ See Carmichael's Lambda Theorem for the general result.

We have $$32760 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$$ By the Chinese remainder theorem, $$U(32760) \cong U(8) \times U(9) \times U(5) \times U(7) \times U(13) \cong C_2 \times C_2 \times C_6 \times C_4 \times C_6 \times C_{12}$$ which has exponent $$12$$.

In terms of congruences, by Euler–Fermat we have

$$\quad a^2 \equiv 1 \bmod 8$$

$$\quad a^6 \equiv 1 \bmod 9$$

$$\quad a^4 \equiv 1 \bmod 5$$

$$\quad a^6 \equiv 1 \bmod 7$$

$$\quad a^{12} \equiv 1 \bmod 13$$

and so $$a^{12} \equiv 1 \bmod 8,9,5,7,13$$

By the Chinese remainder theorem,

$$\quad a^{12} \equiv 1 \bmod 32760$$