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