<s>[INST] Trouble with elementary number theory I'm trying to solve the following two problems:

Show $n^{12}\equiv 1\pmod{72}$ when $(72,n)=1$

and

Compute ${7^8}^9\pmod{100}$

For the first, I saw that $n^{24}=n^{\varphi(72)}\equiv1\pmod{72}$ by Euler's theorem, but this leaves us with $n^{12}n^{12}\equiv 1\pmod{72}$. This could mean $n^{12}\equiv 1\pmod{72}$ or $n^{12}\equiv 71\pmod{72}$. I'm not sure how to argue correctly to conclude it's only $n^{12}\equiv 1\pmod{72}$.
For the second one, I practically did brute force. ${7^8}^9\pmod{100}$ can be solved by considering $8^{9}\pmod{\varphi(100)=40}$. Since $8$ is cyclic with order $4: 8^5\equiv 8\pmod{40}$, we know $8^9=8^5\cdot8^4\equiv 8^5\equiv 8$. So look at $7^8\pmod{100}$. 7 is also cyclic with $7^4\equiv 1\pmod{100}$. So $7^8=(7^4)^2\equiv 1\pmod{100}$. I knew these "cyclic" things by manually computing and reducing, though.
Thank you for any help... (note this is not homework)
 [/INST] For problem 2, you can do better than manually checking by using the Chinese Remainder Theorem. 
Indeed, you first want to compute $x^9$ modulo $\phi(100)=\phi(2^2\times 5^2) = 2\times 4\times 5$. But working modulo $40$ is equivalent, by the Chinese Remainder Theorem, to working modulo $8$ and modulo $5$. The advantage is that $8^9\equiv 0 \pmod{8}$, and $8^9 \equiv 8\pmod{5}$ (since $\varphi(5)=4$, so $8^4\equiv 1\pmod{5}$). Since $8^9\equiv 8\pmod{8}$ and $8^9\equiv 8\pmod{5}$, then it follows that $8^9\equiv 8\pmod{40}$. 
Then you can do the same thing with $7^8\pmod{100}$. Working modulo $4$ we have $7^8\equiv (-1)^8 \equiv 1\pmod{4}$, and working modulo $25$ we have $7^8\equiv (49)^4\equiv (-1)^4\equiv 1\pmod{25}$. So $7^8\equiv 1\pmod{100}$, and we are done.
The first problem is likewise simpler to do by working modulo $8$ and modulo $9$ separately, and then applying the Chinese Remainder Theorem.
</s>