Prove that, given positive integers m and n, if m | n then 2^m − 1 | 2^n − 1. In particular, deduce that if 2^n − 1 is prime then n is prime.

Question

I think I have the first part of the proof down but I would like to double check that my logic works:

m|n $\Leftrightarrow$ n = k*m $\Rightarrow$ $2^n-1 = 2^{km}-1$
$2^{km}-1$=$(2^m)^k-1^k=(2^m-1)((2^m)^{k-1}+\ldots + 1)$
So $2^n-1=(2^m-1)((2^m)^{k-1}+\ldots + 1)$.

Therefore, because m|n, we know $2^m-1|2^n-1$.

Does this proof work? Also, if it does, how do I deduce that if $2^n − 1$ is prime then n is prime? And does "deduce" mean prove that this is also true?

Answer 1

Induction is the easy way to go here. Show that if $(2^m-1)| (2^{km}-1)$ for some $k$, then $(2^m-1)| (2^{(k+1)m}-1)$.

$2^{(k+1)m}-1 = 2^{km}\cdot 2^m - 1 = (2^{km} - 1)2^m + 2^m - 1$

Can you complete the proof?

For the last part, consider the contrapositive of the statement.

Answer 2

Your proof works well.

If $n$ is not prime, then $n=k\cdot m$ for some $n>m>1$. But then $2^m-1$, which is bigger than $1$ and less than $2^n-1$, divides $2^n-1$ (as you have just shown), so $2^n-1$ wouldn't be prime.