# Passing the fermat test

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?

• 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}.$$ – Daniel Fischer Jan 20 '16 at 15:23
• @DanielFischer How did you obtain the LHS? – user2850514 Jan 20 '16 at 15:51
• Plug $m = p^2$ into $b^{m-1}\equiv 1 \pmod{m}$. – Daniel Fischer Jan 20 '16 at 15:53
• Where did you obtain $b^{m-1} \equiv 1$ (mod $m$)? – user2850514 Jan 20 '16 at 15:55
• 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. – 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$
• 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$? – user2850514 Jan 20 '16 at 16:23
• @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. – Kevin Jan 21 '16 at 9:24