 mersenneforum.org > Math A Mersenne number exercise
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2018-01-09, 12:00   #1
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

28810 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 1,657 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 165710 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 3×53×31 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

Then, for example:

is an integer for all integer values of x and n.
And:

Generalised:

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:

Therefore:

As above:

It follows:

So:

And f(x) is an integer, so divides 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

26×131 Posts Quote:
 Originally Posted by lukerichards I think this is sufficient? NB Spoiler below. If Then, for example: is an integer for all integer values of x and n. And: Generalised: 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: Therefore: As above: It follows: So: And f(x) is an integer, so divides 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

1001000002 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

1,657 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

1,657 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

20C016 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   Thread Tools Show Printable Version Email this Page 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 18:44.

Sat Apr 17 18:44:51 UTC 2021 up 9 days, 13:25, 0 users, load averages: 1.73, 1.57, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.