Suppose $M_m = 2^m - 1$ is a number that is known to be composite, and $m$ is prime.
However, how do I show that it satisfy the property of $2^{M_m} \equiv 2 \pmod {M_m}$ such that it is a pseudo-prime? Using this fact, it is also required to show that there are infinitely many pseudo-primes.
I have gotten stuck after these steps:
Start with $2^{M_m}$, expanding it to get $2^{(2^m-2) +1} = 2\cdot2^{(2^m-2)}$.
But how does the above link to what I'm trying to achieve? I don't have a clear strategy here.
I'd prefer to do it in a slightly different fashion. Suppose that $m$ is a number such that $2^m\equiv 2\pmod m$ ($m$ itself can be prime or composite, we just don't care; in the latter case it is also called pseudoprime). Then the number $M=2^m-1$ has the same property: $2^M\equiv 2\pmod M$. How so?
Well, just like that: $x^n-1$ is divisible by $x-1$ (which is easily proved by induction), hence $2^{m}-1\mid2^n-1$ whenever $n$ is a multiple of $m$. But wait, I vaguely remember seeing an exponent $2^m-2$ not so long ago, and the number $2^m-2\equiv0\pmod m$, which is just a long-winded way to say that it is a multiple of $m$. There must be certain consequences for $2^{2^m-2}-1$. Can you continue?
So we have an infinite sequence of numbers that are either prime or pseudoprime. Prove that a composite $m$ must produce a composite $M$, find one such number, and the infinitude of pseudoprimes will follow trivially.