Problem regarding Euler's Theorem: $a^{\phi(n)}\equiv 1 \bmod n$

Here's the problem:

If $n \geq 2$, and if $p$ is a prime number s.t $p|n$ but $p^2$ is not a factor of $n$, then $$p^{\phi(n)+1}\equiv p \mod n$$

So since we're dealing with Euler's Phi function, I figured that this was an application of Euler's Theorem (please correct me if I am wrong). An attempt (though miniscule):

Attempted Proof

We know that $p|n$, so $\exists q \in \mathbb{Z}$ s.t $$n=pq.$$ However, since $p^2$ is not a factor of n, we know that these integers are relatively prime to eachother. Thus, $\exists r,t \in \mathbb{Z}$ s.t $$1=p^2r+nt$$ Now if we consider the integers modulo n, we see that $p^2$ is invertible since it is relatively prime to $n$ and that $r$ happens to be our inverse. Thus, we can say that $$1=p^2r + nt$$ $$\implies 1-p^2r=nt$$ $$\implies [1-p^2r]_n=_n$$ $$\implies [p^2]_n[r]_n=_n$$ So $r$ must be the inverse of $p^2$.

Okay so I'm sure I've gone off into a tangled direction. So my question is: how am I to finally get to the $\phi$ function? I mean, considering how Euler's Theorem goes, we know that we have $$a^{\phi(n)} \equiv 1 \mod n$$ So wouldn't it follow naturally that $$a^{\phi(n)+1}\equiv a \mod n$$ ????

For our problem, we of course have $a=p$.

• Maybe you can use the fact that $\phi(p) = p-1$? – Elliot Gorokhovsky Jul 20 '14 at 22:02
• But $p^2$ is not relatively prime to $n$ ($p$ is a prime dividing $n$) and $p^2$ cannot have a multiplicative inverse! – Jeppe Stig Nielsen Jul 20 '14 at 22:07
• Hint: since $\,p,q\,$ are coprime, $\, pq\mid x\iff p\mid x\,$ and $\,q\mid x.\,$ That $\,p\mid x\,$ is clear, and $\,q\mid x\,$ follows by Euler. – Bill Dubuque Jul 20 '14 at 22:08
• OP: Yes, $p$ and $q$ are coprime, that doesn't mean $n$ and $p^2$ are coprime. – blue Jul 20 '14 at 22:09
• @blue $\ p\,$ is coprime to $\,q = n/p\,$ (else $\,p\mid n/p\,\Rightarrow\, p^2\mid n).\ \$ – Bill Dubuque Jul 20 '14 at 22:11

Show it's true mod $p$ and mod $n/p$, invoking the Chinese Remainder Theorem. (Or a simpler divisibility version, $ab\mid x\iff a\mid x$ and $b\mid x$ when $a,b$ are coprime, as Bill suggests.)
We know that $p|n$ $\implies$ $\exists \gamma \in \mathbb{Z^{+}}$ s.t $n=p\gamma$. We are given the $p^2$ is not a factor of $n$ $\implies p^2 > n$ and so $p$,$\gamma$ share no common divisors. Thus, $\gcd(p,\gamma)=1$. Then by Euler's Theorem, we have
$$p^{\phi(\gamma)} \equiv 1 \mod p$$
Since $\phi(n)=\phi(p)\phi(\gamma)$, it follows that
$$p^{\phi(p) \cdot \phi(\gamma)} \equiv 1 \mod p \implies (p^{\phi(\gamma)})^{\cdot \phi(p)} \equiv 1 \mod \gamma$$ $$\implies p^{\phi(n)} \equiv 1 \mod \gamma$$ So it follows that $\gamma | (p^{\phi(n)} - 1)$ $\implies$ $\gamma \cdot p |(p^{\phi(n)+1}-p)$ $\implies$ $n|(p^{\phi(n)+1}-p)$. Hence $$p^{\phi(n)+1} \equiv p \mod n$$