I came across this Theorem in "Elementary Number theorem" by David B. Burton :
"If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one."
I am not able to understand why this result holds only for odd pseudo prime number ?
There has been a discussion on the proof earlier, but I can't find any discussion for the odd case.
The proof in the book goes as:
Because n is a composite number, we can write $ n = rs$, with $ 1 < r \leq s < n$. Then $ 2^r -1 \mid 2^n-1 $, or equivalently $2^r – 1 \mid M_n $ making $M_n $ composite. By hypothesis, $2^n \equiv 2 $(mod n) ; hence $2^n-2 = kn $ for some integer k. It follows that
$ 2^ {M_n-1} $ = $2^{2^n-2}$ = $2^{kn} $
This yields
$ 2^ {M_n-1} – 1 $ = $2^{kn} – 1 $
= $ 2^ {n-1} $ ($ 2^ {n(k-1)} $ + $ 2^ {n(k-2)} $ + … + $ 2^ {n} $ + 1 )
= $M_n$ ($ 2^ {n(k-1)} $ + $ 2^ {n(k-2)} $ + … + $ 2^ {n} $ + 1 )
$\equiv 0$ ( mod $M_n$)
We see immediately that $2^{M_n} – 2 \equiv 0 (mod M_n) $, in light of which $M_n$ is pseudoprime.
Best Answer
If $n|2^n-2$, let $2^n-2=nm$. Then we want to prove $M_n=2^n-1|2^{M_n}-2=2^{2^n-1}-2$. But $2^{2^n-1}-2=2 \cdot2^{2^n-2}-2=2(2^{nm}-1)$. $m$ is even, so let $m=2k$ Then $2^{2^n-1}-2=2(2^{2nk}-1)=2(2^{nk}+1)(2^{nk}-1)$ and we know $2^n-1|2^{nk-1}$ so $M_n|2^{M-n}-2$