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=[0]_n$$ $$\implies [p^2]_n[r]_n=[1]_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$.

  • $\begingroup$ Maybe you can use the fact that $\phi(p) = p-1$? $\endgroup$ – Elliot Gorokhovsky Jul 20 '14 at 22:02
  • 1
    $\begingroup$ But $p^2$ is not relatively prime to $n$ ($p$ is a prime dividing $n$) and $p^2$ cannot have a multiplicative inverse! $\endgroup$ – Jeppe Stig Nielsen Jul 20 '14 at 22:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 20 '14 at 22:08
  • 1
    $\begingroup$ OP: Yes, $p$ and $q$ are coprime, that doesn't mean $n$ and $p^2$ are coprime. $\endgroup$ – blue Jul 20 '14 at 22:09
  • $\begingroup$ @blue $\ p\,$ is coprime to $\,q = n/p\,$ (else $\,p\mid n/p\,\Rightarrow\, p^2\mid n).\ \ $ $\endgroup$ – 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.)


I think I've got it now:

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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.