 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

25×32 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 26158 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 101100011012 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 22·7·11·37 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

28810 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

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

142110 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 1001000002 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

72×29 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   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 04:54.

Fri Aug 7 04:54:40 UTC 2020 up 21 days, 41 mins, 1 user, load averages: 1.58, 1.85, 1.87