mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-01-09, 12:00   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default 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?
lukerichards is offline   Reply With Quote
Old 2018-01-09, 12:32   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

142410 Posts
Default

Hint: for any odd prime number q, 2 is a square (mod q) if and only if \(q\equiv\pm1\pmod{8}\).
Nick is offline   Reply With Quote
Old 2018-01-10, 13:30   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24·89 Posts
Default

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
Nick is offline   Reply With Quote
Old 2018-01-11, 01:03   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

101·113 Posts
Default

Nothing like a little quadratic-residuacity exercise to get the new(ish) year off to a good start, eh?
ewmayer is online now   Reply With Quote
Old 2018-01-14, 20:53   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by Nick View Post
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
lukerichards is offline   Reply With Quote
Old 2018-01-14, 21:22   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-14, 21:48   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
There are
SPOILER
Which, when used, ruin the latex :P
lukerichards is offline   Reply With Quote
Old 2018-01-15, 15:03   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24×89 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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 \]
Nick is offline   Reply With Quote
Old 2018-01-15, 15:21   #9
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts
Default

I want to start thinking about the next point, but I've got actual work to do during the day!
lukerichards is offline   Reply With Quote
Old 2018-01-15, 15:26   #10
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

101100100002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Note the recurrence...
Nice!
Nick is offline   Reply With Quote
Old 2018-01-15, 20:02   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Nick View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Tue Aug 11 06:53:37 UTC 2020 up 25 days, 2:40, 1 user, load averages: 2.21, 2.38, 2.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.