 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

11B16 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 25778 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 3·7·67 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×5,639 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

11B16 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

100000110000002 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

283 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

3×7×67 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 11B16 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

3×7×67 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 21:22.

Sat Jul 4 21:22:41 UTC 2020 up 101 days, 18:55, 1 user, load averages: 1.40, 1.52, 1.48