Demostremos la proposición contra positiva, esto es, si n no es primo (es decir, un número compuesto) entonces 2n−1 no es primo (es decir, un número compuesto).
Como n es un número compuesto se puede descomponer como producto n=ab con a,b>1.
Entonces habrá que probar que 2ab−1 es compuesto. Notemos que 2ab−1=(2a)b−1b.
Usando la sugerencia, se observa que 2a−1 divide a (2a)b−1b. Como 2a−1 es mayor a uno y estrictamente menor a (2a)b−1b, como lo muestran los cálculo de más abajo, llegamos a la conclusión de que (2a)b−1b=2n−1 no es primo (es decir, es compuesto).
Aquí las cuentas de las que hablábamos:
Como a>1 se tendrá que 2a>2, restando 1 de ambos lados llegamos a que 2a−1>1.
Por otro lado, 2a<(2a)b pues b>1, por tanto 2a−1<2ab−1. Como queríamos demostrar.