View Single Post
Old 2018-01-14, 20:53   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by Nick View Post
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
lukerichards is offline   Reply With Quote