Prove the following statement:

If an odd natural number $n$ passes the Miller-Rabin primality test (MRT) to base $2$, $n$ also passes the Fermat test to base $2$.

My attempt:

Let $n \in \mathbb{N}, n \equiv 1 \mod 2$. $n$ passes the MRT.

The Fermat test to base $2$ is passed if $2$ and $n$ are relatively prime and

$$2^{n-1} \equiv 1 \mod n$$

Obviously $2$ and $n$ are relatively prime since $n$ is odd.

Now, let $n-1 = d \cdot 2^{\displaystyle s}$ with $d$ being odd.

if $n$ passes the MRT, then either $$2^{\displaystyle d} \equiv 1\pmod{n} $$

or, $$2^{\displaystyle d \cdot 2^{\displaystyle r}} \equiv -1\pmod{n}$$ where $0\leq r \lt s$.

If the first congruence holds, then obviously

$$2^{\displaystyle d} \equiv (2^{\displaystyle d})^{\displaystyle 2^{\displaystyle s}} \equiv 2^{\displaystyle n-1} \equiv1\pmod{n} .$$ If the second congruence holds, then $$2^{\displaystyle d \cdot 2^{\displaystyle r+1}} \equiv 1\pmod{n}$$

and since $r+1 \leq s$, we then get (with repeated exponentiation with $2$) $$2^{\displaystyle d \cdot 2^{\displaystyle s}} \equiv 1\pmod{n}.$$

Thus, we have shown that $n$ also passes the Fermat test for both cases and we have proved our conjecture.

  • 1
    $\begingroup$ Looks right to me. The last step, going from $r+1$ to $s$ in the exponent, is correct because $r+1 \leq s$ and you might want to supply reasoning for that last step. $\endgroup$ – Mark Fischler Aug 31 '16 at 16:18
  • 1
    $\begingroup$ $\scriptstyle 2^{ 2^{\displaystyle 2^2}}$ $\text{\$\scriptstyle 2^{2^{\displaystyle 2^2}}\$ }$ $\endgroup$ – reuns Aug 31 '16 at 16:32

Your Answer

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

Browse other questions tagged or ask your own question.