I have seen quite a few proofs of Euler's Totient Theorem that $a^{\phi(n)}≡1 \pmod n$ for all $a$ relatively prime to $n$. However, none have been done using induction. That is what I have been tasked with, and I do not know where to start.
This is the hint I have been given by the instructor: "Go by (strong) induction on $n$ this time. It breaks into cases of whether $n$ is composite or a power of a prime. I needed a second induction for a power of a prime."
We sketch one of the inductions. Suppose that $n$ is composite but not a prime power. Then $n=kl$ for some relatively prime integers $k$ and $l$ with $k\lt n$, $l\lt n$. By the (strong) induction hypothesis, we have $a^{\varphi(k)}\equiv 1\pmod k$ and $a^{\varphi(l)}\equiv 1\pmod l$. It follows that $(a^{\varphi(k)})^{\varphi(l)}\equiv 1\pmod{k}$, with a similar result if we interchange the roles of $k$ and $l$.
Thus $a^{\varphi(k)\varphi(l)}\equiv 1\pmod{k}$ and $\pmod{l}$, and therefore $\pmod{kl}$. This finishes the induction, since $\varphi(k)\varphi(l)=\varphi(kl)$.