For two distinct primes $p,q$, show that $p^{q^3+q} = p^2$ (mod $q$).
Since $gcd(p,q)=1$, it suffices to show that $pq|p^{q^3+q}-p^2$, since $p$ obviously divides that, but I don't know how to proceed from there. There is a lemma in the book that says if $p,q$ are distinct primes with $a^p=a$ (mod $q$) and $a^q=a$ (mod $p$), then $a^{pq} = a$ (mod $pq$), but I'm not sure how to go about applying that.
First we observe that $$p^{q^3+q}=p^{q^3-1+q+1}=p^{(q-1)(q^2+q+1)+q-1+2}$$ Now using the fact that $p^{q-1}=1 \pmod q$. We can conclude that it is $p^2 \pmod q$