Let $p$ be a prime and $b\in\mathbb{Z}$ where ${\rm gcd}(b,~p)=1$. Prove that $b$ passes the Fermat test test for $m=p^2$ if and only if $b^{p-1}\equiv1$ mod $p^2$.

We show this is true in both directions. Suppose $b$ passes the Fermat test, so that

$$a^{b-1} \equiv 1~{\rm mod}~b,$$

What does $m=p^2$ mean? How do I continue this proof?

  • 1
    $\begingroup$ It's not particularly well phrased. What you are meant to show is that $$b^{p^2-1} \equiv 1 \pmod{p^2} \iff b^{p-1} \equiv 1 \pmod{p^2}.$$ $\endgroup$ – Daniel Fischer Jan 20 '16 at 15:23
  • $\begingroup$ @DanielFischer How did you obtain the LHS? $\endgroup$ – user2850514 Jan 20 '16 at 15:51
  • $\begingroup$ Plug $m = p^2$ into $b^{m-1}\equiv 1 \pmod{m}$. $\endgroup$ – Daniel Fischer Jan 20 '16 at 15:53
  • $\begingroup$ Where did you obtain $b^{m-1} \equiv 1$ (mod $m$)? $\endgroup$ – user2850514 Jan 20 '16 at 15:55
  • $\begingroup$ That's the Fermat test for base $b$ and possible prime $m$. While usually one would say that $m$ passes the Fermat test with base $b$ when $b^{m-1}\equiv 1 \pmod{m}$, here the authors say that the base $b$ passes the test in that case. $\endgroup$ – Daniel Fischer Jan 20 '16 at 15:58

This is the sketch of a proof. Assume that $$b^{p^{2}-1} \equiv 1 \quad \pmod{p^{2}}$$ then since $p$ is prime we can write $b^{p} \equiv b \pmod{p}$, or alternatively $$b^{p} = jp+b$$ for some integer $j$.

Then move to the binomial theorem, \begin{align} b^{p^{2}}&=(jp+b)^{p} \\ &= b^{p}+\binom{p}{p-1}pb^{p-1}jp+\binom{p}{p-2}b^{p-2}j^{2}p^{2}+\ldots \end{align} Every term on the right hand side here contains a factor of $p^{2}$, other than $b^{p}$. Hence $$b^{p} \equiv b^{p^{2}} \quad \pmod{p^{2}}$$ this is equivalent to saying \begin{align} b^{p-1} &\equiv b^{p^{2}-1} \\ &\equiv 1 \quad \pmod{p^{2}} \end{align} Quick Edit By the way, we can take this last step (i.e, dividing by $b$) since $\gcd(b, p)=1$

  • $\begingroup$ You state since $p$ is prime we can write $b^p\equiv b~({\rm mod}~p^2)$, how is this true? Also your next step you state $b^p = jp +b$, should this be $b^p=jp^2+b$? $\endgroup$ – user2850514 Jan 20 '16 at 16:23
  • $\begingroup$ @user2850514 Good spot - I have changed the $\pmod{p^{2}}$ to $\pmod{p}$ which then means we can write, wlog $b^{p}=jp+b$. Many thanks. $\endgroup$ – Kevin Jan 21 '16 at 9:24

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.