I take it you want to show that for any $n$ and for any $(a,n)=1$, $$\tag 1 a^{\varphi(n)}=1\mod n$$
As you said, it suffices to show that $\Bbb Z_n^\times$ is a group under multiplication.
But one can show $k$ is invertible mod $n$ iff $(k,n)=1$, by Bezout. Note that if $(k,n)=1$; we know there are $s,t$ with $ks+nt=1$, and $ks=1\mod n$; and moreover we have $(s,n)=1$ by the same equation that witnessed $(k,n)=1$.
Then $(k,n)=(k',n)=1\implies (kk',n)=1$. Thus $\Bbb Z_n^\times $ is a group under multiplication. It has order $\varphi(n)$, so by Lagrange's thorem $(1)$ holds for any $a$.
Theorem: If $b$ and $c$ are non-negative natural numbers, $m$ and $a$ are co-prime, $b = c\enspace\text{mod}\,\varphi(m)$, then $a^b = a^c\enspace\text{mod}\,m$.
Proof: Without loss of generality, suppose that $b>c$. Then $b=c+k\cdot\varphi(m)$ where $k$ is a natural number. $$a^b = a^{c+k\cdot\varphi(m)} = a^c\cdot (a^{\varphi(m)})^k = a^c \enspace\text{mod}\,m$$
Where we used Euler's theorem for $a^{\varphi(m)} = 1\enspace\text{mod}\,m$, and the fact that $$a'=a''\enspace\text{mod}\,m\,\land\,b'=b''\enspace\text{mod}\,m\implies a'b'=a''b''\enspace\text{mod}\,m$$
End of proof.
Suppose we want to calculate $a^{a^{320}}$ modulo $1000$. We can first calculate $a^{320}$ modulo $\varphi(1000)=400$ since $a$ and $1000$ are co-prime, using the theorem above.
To calculate $a^{320}$ modulo $400$, we can calculate $320$ modulo $\varphi(400)=160$, because, again, $400$ and $a$ are co-prime.
$$320 = 0\enspace\text{mod}\,160 \implies a^{320} = 1\enspace\text{mod}\,400 \implies a^{a^{320}}=a\enspace\text{mod}\,1000 $$
And because $a=531\enspace\text{mod}\,1000$, then
$$a^{a^{320}}=531\enspace\text{mod}\,1000 $$
Best Answer
By induction. If $n=1$, then it is true. If $n\ge2$, then
$a^{p^{n-1}} \equiv 1 \bmod p^{n} \implies (a^p)^{p^{n-2}} \equiv 1 \bmod p^{n} \implies (a^p)^{p^{n-2}} \equiv 1 \bmod p^{n-1} \implies a^p \equiv 1 \bmod p$
By Fermat, $a^p \equiv a \bmod p$ and so $a \equiv 1 \bmod p$.
By induction. If $n=1$, then it is true. If $n\ge2$, then
$a^{p^{n-1}} = (a^{p^{n-2}})^p = (1+b p^{n-1})^p \equiv 1 \bmod p^{n}$
by the binomial theorem.