"If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one."
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. // //
My question is when does the assumption , n is an "odd"(in particular) pseudoprime being used. I cant see it clearly.
For which odd integers $n\ge 3$ is $$2^n-1$$ a poulet-number (pseudoprime with respect to base $2$) ?
The condition is that $$2^{2^n-2}\equiv 1\mod (2^n-1)$$ holds and $$2^n-1$$ is composite.
Let $k$ be the order of $2$ modulo $2^n-1$, in other words the smallest positive integer such that $2^k\equiv 1\mod n$. Clearly, we have $k=n$
We can conclude that $n$ must be a divisor of $2^n-2$ , so $n$ must either be prime or a poulet-number. Conversely, if $n$ is a poulet-number, then $n$ divides $2^n-2$ , hence $2^n-1$ is again a poulet-number.
Hence , if $n$ is not prime , then $n$ is a poulet-number if and only if $2^n-1$ is a poulet-number.