Thread: A Mersenne number exercise View Single Post
2018-01-14, 21:22   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by lukerichards 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.
There are
SPOILER
tags

But I know I can beat that in simplicity.

Note the reccurence:

[TEX]M_n=2M_{n-1}+1=2M_{n-1}+M_1[/TEX]

This leads to [TEX]2^y(M_n)+M_y=M_{n+y}[/TEX] which when reccursively applied shows the statement.

Last fiddled with by science_man_88 on 2018-01-14 at 21:50