Solving question using induction as a previous part

Question

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.

The second statement is clearly false: $2\cdot9-1=17$ is prime even though $9$ is not prime. — barak manos, Nov 30 '16 at 17:23
I think that he refers to $2^N-1$ is prime if $N$ is prime, this is a well-known property. — Ricardo Largaespada, Nov 30 '16 at 17:43

Ricardo Largaespada · Accepted Answer · 2016-11-30T17:57:11.863

0

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$.

edited Nov 30 '16 at 17:57

answered Nov 30 '16 at 17:50

Ricardo Largaespada

680

Solving question using induction as a previous part

1 Answers1