mersenneforum.org > Math A Mersenne number exercise
 Register FAQ Search Today's Posts Mark Forums Read

2018-01-09, 12:00   #1
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
A Mersenne number exercise

Hi,
I've seen the following statement in a paper but I don't have access to the reference given. Could someone maybe help me with a proof, please?

Quote:
 If: p is a prime > 2 Mp = 0 mod q Then: q = 1 mod p and q = +- mod 8
Not sure where to start?

 2018-01-09, 12:32 #2 Nick     Dec 2012 The Netherlands 101101000002 Posts Hint: for any odd prime number q, 2 is a square (mod q) if and only if $$q\equiv\pm1\pmod{8}$$.
 2018-01-10, 13:30 #3 Nick     Dec 2012 The Netherlands 5A016 Posts 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$$. Let q be an odd prime number. 2. Show for all positive integers m,n with m>n that if q divides $$2^m-1$$ and q divides $$2^n-1$$ then q divides $$2^{m-n}-1$$. Let p be an odd prime number as well and suppose that q divides $$2^p-1$$. 3. Show for all positive integers n that q divides $$2^n-1$$ if and only if p divides n. 4. Conclude that $$q\equiv 1\pmod{p}$$. 5. Show that 2 is a square in the integers modulo q, and conclude that $$q\equiv\pm1\pmod{8}$$. For the last part, the first example here may be useful. Last fiddled with by Nick on 2018-01-10 at 16:09 Reason: Clarification
 2018-01-11, 01:03 #4 ewmayer ∂2ω=0     Sep 2002 República de California 2·13·443 Posts Nothing like a little quadratic-residuacity exercise to get the new(ish) year off to a good start, eh?
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

2018-01-14, 21:22   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 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

2018-01-14, 21:48   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by science_man_88 There are SPOILER
Which, when used, ruin the latex :P

2018-01-15, 15:03   #8
Nick

Dec 2012
The Netherlands

26408 Posts

Quote:
 Originally Posted by lukerichards I think this is sufficient?...
Yes, that's fine.
You can also visualize it by writing the numbers in binary.
For example, $$2^4-1$$ is a factor of $$2^{12}-1$$ as
$\underbrace{1111}\underbrace{1111}\underbrace{1111}=1111\times 100010001$

 2018-01-15, 15:21 #9 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 12016 Posts I want to start thinking about the next point, but I've got actual work to do during the day!
2018-01-15, 15:26   #10
Nick

Dec 2012
The Netherlands

26408 Posts

Quote:
 Originally Posted by science_man_88 Note the recurrence...
Nice!

2018-01-15, 20:02   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Nick Nice!
Not only that, this solves ( or at least heuristics) the first 3 all wihout direct invocation of fermat's little theorem.

1) noted above.
2)see formula from 1, M_m= 2^{m-n}M_n+M_{m-n} q divides the first term, and so q must divide into the second term in order to divide the LHS.
3) following from 2, if q divides other mersennes other than multiples, it follows there is no minimal p, this leads to the absurdity that 1/ q is integer.

Last fiddled with by science_man_88 on 2018-01-15 at 20:03

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 7 2013-09-20 11:20 jasong jasong 1 2013-04-07 05:55 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 kurtulmehtap Math 12 2010-05-03 14:02 sean Factoring 2 2006-10-23 21:08

All times are UTC. The time now is 15:06.

Sun Sep 27 15:06:03 UTC 2020 up 17 days, 12:17, 1 user, load averages: 1.80, 1.48, 1.37

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.