# Proving that a number that passes the Miller-Rabin primality test also passes the Fermat test

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^s$ with $d$ being odd.

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

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

If the first congruence holds, then obviously

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

and since $r+1 \leq s$, we then get (with repeated exponentiation with $2$) $$2^d \cdot 2^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.

• 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. – Mark Fischler Aug 31 '16 at 16:18
• $2^{ 2^2^2}$ $\text{\$\scriptstyle 2^{2^{\displaystyle 2^2}}\$}$ – reuns Aug 31 '16 at 16:32