Thread: A Mersenne number exercise View Single Post
2018-01-14, 20:53   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by Nick As this is related to Mersenne numbers, let's turn it into an exercise for anyone interested. 1. Show for all positive integers m,n that if m divides n then $$2^m-1$$ divides $$2^n-1$$.
I think this is sufficient?
NB Spoiler below.

If $f(x, n) = \sum_{k=1}^{(x)} (2^{n})^{k-1}$

Then, for example:
$\ f(3, n) = (2^{n})^2 + (2^{n}) + 1$

$f(x, n)$ is an integer for all integer values of x and n.
And:
$({2^n} - 1)f(3, n) = (2^{n})^3 - 1$

Generalised:

$({2^n} - 1)f(x, n) = (2^{n})^x - 1$
This is an integer for all integer values of n and x.

Now, if n|m, then m = x * n, where m, n and x are all integers.

So:

$2^{m} = 2^{xn} = (2^n)^x$

Therefore:

$2^{m} - 1 = 2^{xn} - 1 = (2^n)^x - 1$

As above:

$(2^n)^x - 1 = ({2^n} - 1)f(x, n)$

It follows:

$\frac{(2^n)^x - 1}{({2^n} - 1)}\ = f(x, n)$

So:

$\frac{2^m - 1}{({2^n} - 1)}\ = f(x, n)$

And f(x) is an integer, so $M_n$ divides $M_m$ when n divides m.

Last fiddled with by lukerichards on 2018-01-14 at 20:56