Solving question using induction as a previous part

33 Views Asked by At

Prove (for example by induction on n) that $2^{mn} −1$ is an integer multiple of $2^m −1$, where $m,n \in \mathbb{N}$

Explain why this implies that $2^N −1$ for $N\in \mathbb N$ can only be prime if $N$ is prime.

I have already proved by induction that $2^{mn} −1$ is an integer multiple of $2^m −1$ but am unsure of how to use this to explain $2^N −1$ for $N \in \mathbb N$ can only be prime if $N$ is prime.

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming that $N$ is composite, then $N=ab$, where $a,b$ are positive integers greater than $1$.

$$ 2^N-1=(2^a)^b-1$$ $$ 2^N-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots +2^a+1)$$

And clearly $2^N-1$ is not prime, because is the product of two numbers greater than $1$.