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)

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.
