A Mersenne number exercise

lukerichards · 2018-01-09, 12:00

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
M_p = 0 mod q
Then:
q = 1 mod p
and
q = +- mod 8

Not sure where to start?

Nick · 2018-01-09, 12:32

Hint: for any odd prime number q, 2 is a square (mod q) if and only if $q\equiv\pm1\pmod{8}$.

Nick · 2018-01-10, 13:30

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.

ewmayer · 2018-01-11, 01:03

Nothing like a little quadratic-residuacity exercise to get the new(ish) year off to a good start, eh?

lukerichards · 2018-01-14, 20:53

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.

science_man_88 · 2018-01-14, 21:22

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.

lukerichards · 2018-01-14, 21:48

Quote:

Originally Posted by science_man_88

There are
SPOILER

Which, when used, ruin the latex :P

Nick · 2018-01-15, 15:03

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 \]

lukerichards · 2018-01-15, 15:21

I want to start thinking about the next point, but I've got actual work to do during the day!

Nick · 2018-01-15, 15:26

Quote:

Originally Posted by science_man_88

Note the recurrence...

Nice!

science_man_88 · 2018-01-15, 20:02

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.

2018-01-09, 12:32	#2
Nick Dec 2012 The Netherlands 2⁴·101 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 3120₈ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Exercise for gaming time	jasong	jasong	7	2013-09-20 11:20
Is an online exercise game not based on trust doable?	jasong	jasong	1	2013-04-07 05:55
Number of distinct prime factors of a Double Mersenne number	aketilander	Operazione Doppi Mersennes	1	2012-11-09 21:16
Number of Factors for a Mersenne Number	kurtulmehtap	Math	12	2010-05-03 14:02
Exercise 1.23 in Crandall & Pomerance	sean	Factoring	2	2006-10-23 21:08

2018-01-11, 01:03	#4
ewmayer ∂²ω=0 Sep 2002 República de California 2·7·829 Posts	Nothing like a little quadratic-residuacity exercise to get the new(ish) year off to a good start, eh?

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