Stuck on middle step of proof that $a^{p(p-1)}=1 \pmod{p^2}$

I have a question on my homework that says to prove $a^{p(p-1)}\equiv 1 \pmod{p^2}$ and hints at using the proof for fermats little theorem as something to get us started. A TA also hinted at using Euler's totient function -- which we haven't proved or done much with.

Mirroring the FLT proof, here's what I was thinking so far:

Define the set $S_{1}= [{1,2,3,4,\ldots,p^2-1}]$. Define another set $S_{2}= [{1a,2a,3a,4a,\ldots,(p^2-1)a}]$

Since they hinted to mimic FLT proof, Im thinking that I prove that the sets are equal. I can do that by saying $S_{1}$ is a subset of $S_{2}$ and $S_{2}$ is a subset of $S_{1}$.

But I don't know how to proceed from there. I also have no idea about the totient function and how that's relevant.

I think once I find out how to say $S_{1} = S_{2}$ I can say, like how we do for FLT, that their products are equal.

Then somehow leading it back to $(p^2-1)! = a^{p^2-1}(p^2-1)$, and saying that since p is prime, $p^2-1$ must have an inverse $\bmod p$ and using that to say that yes indeed $a^{p(p-1)}\equiv1\pmod{p^2}$

I guess I'm just stuck on the middle step -- proving the sets are equal

EDIT: Forgot to mention that we're given $\gcd(a,p) = 1$

Here is a proof. By Fermat $a^{p-1}\equiv 1\mod p$, so $a^{p-1}=kp+1$ for some $k$. Then $a^{p(p-1)}=(kp+1)^p$. By the binomial formula,

$$a^{p(p-1)}= (kp)^p+p(kp)^{p-1}+...+p(kp)+1\equiv 1\mod p^2.$$ QED

You have the right idea, but you need to have the condition that $\gcd(a,p)=1$. Then consider $S_1'$ the set of numbers in your $S_1$ which are coprime to $p$. Then define $S_2'$ to be the elements of $S_1'$ multiplied by $a$.

Now you can prove that $S_1'=S_2'$ and so the products of their elements are equal. As the elements of $S_1'$ are invertible modulo $p^2$, you can now claim: $$a^{|S_1'|}\equiv 1 \mod p^2.$$

It remains to check that $|S_1'|=\varphi(p^2)=p(p-1)$.

The problem to your proposed proof is that you have multiples of $p$ in sets $S_1$ and $S_2$, so the products in each set are $\equiv 0 \bmod{p}^2$.

Consider $S_1 = \{k: 0 \leq k \leq p^2-1, \gcd(k, p^2) = 1 \}$, and $S_2 = \{ak: 0 \leq k \leq p^2-1, \gcd(k, p^2) = 1 \}$, where $\gcd(a, p^2) = 1$. Note that $|S_1| = |S_2| = p(p-1)$.

We claim the elements of $S_2$ are unique. If we have two elements $ai$ and $aj$ in $S_2$ such that $ai \equiv aj \pmod{p^2}$, then $a(i-j) \equiv 0 \pmod{p^2}$. Since $\gcd(a, p^2) = 1$, this means $i \equiv j \bmod{p^2}$. Thus, since $k$ ranges over $[0, p^2-1]$, we have that all the elements of $S_2$ are unique.

Since each element of $S_2$ is unique and relatively prime to $p^2$, we can see that in fact each element of $S_2$ is an element of $S_1$, and vice versa. Thus, the products of the two are equal modulo $p^2$: $$\prod_{0 \leq k \leq p^2-1\\ \gcd(k, p^2)=1} k \equiv \prod_{0 \leq k \leq p^2-1\\ \gcd(k, p^2)=1}ak \equiv a^{p(p-1)}\cdot\prod_{0 \leq k \leq p^2-1\\ \gcd(k, p^2)=1} k\pmod{p^2} $$ Since each element of $S_1$ and $S_2$ is relatively prime to $p^2$, we can divide by $\prod_{0 \leq k \leq p^2-1\\ \gcd(k, p^2)=1}k$ to find $$a^{p(p-1)} \equiv 1 \pmod{p^2}$$ as desired.

Special case of: $\ \ \ \underbrace{\begin{align} e\ge 1,\ \,c&\equiv b\!\pmod{\!{{kn^{\large\color{#c00}e}}}}\\ \Longrightarrow\ \ c^{\:\!\large n}&\equiv b^{\large n}\!\!\!\!\pmod{\!kn^{\large\color{#c00} {e+1}}}\end{align}}_{\large \!\text{Lifting The }\color{#c00}{\text{Exponent}}\ \rm (LTE)}\ \ $ Put $\,\ \begin{align} n&= p,\, \ c = a^{\large p-1}\\ e&=1,\ \, b=1,\ k=1\end{align}$

The proof is simple: $ $ note $\,c^n\!-b^n = (c\!-\!b)d,\, d = \sum_{j=0}^{n-1} c^j b^{n-1-j}$ and $\,kn^{\large\color{#c00}e}\!\mid c\!-\!b\,$ and $\,n^{\large\color{#c00}1}\!\mid d,\,\:$ by $\:n\mid c\!-\!b\,\ $ so $\bmod n\!:\ c\equiv b\,\Rightarrow\, c^j\equiv b^j\,\Rightarrow\, d\equiv \sum b^{n-1} \equiv n\cdot b^{n-1}\equiv 0$

See also here and here and AoPS LTE.