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.