using euler's theorem (phi/totient function) to compute order of group elements

Question

The question is to prove that every element of $(Z / 72Z)^{\times}$ has order dividing $12$, somehow using Euler's theorem to first reach the fact that every element has order dividing $24$, and then proceeding from there. I am very confused; I can't see how Euler's theorem/phi function are to be used here.

Answer 1

Hint: By the Chinese remainder theorem, $$ (\mathbb Z / 72\mathbb Z)^{\times} \cong (\mathbb Z / 8)^{\times} \times (\mathbb Z / 9)^{\times} \cong C_4 \times C_6 $$ and $lcm(4,6)=12$.