mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2015-04-06, 03:14   #1
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2×32×5 Posts
Lightbulb Some interesting patterns regarding mod

This has probably been done before and to a much greater depth, but I've discovered some interesting patterns when dividing Mersenne numbers by a small prime and returning the remainder (the modulus operation). My motivation is to remove numbers from the list of primes that one does trial division with (although I wouldn't dare suggest it be incorporated into Prime95 or any other primality test unless it was rigorously proven that a Mersenne number is never divisible by a particular number).

I've also listed "mod 10" for comparison, which is the last digit of the Mersenne number when written in decimal.

Code:
INDEX:     2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61

mod 10:    3  7  1  7  7  1  1  7  7  1  7  1  1  7  7  1  7  1

mod 61:    3  7 31  5 34 17 43 53  9 29 58 54 25 42 16 50 30  1
mod 59:    3  7 31  9 41 49 32 13 46 57 54 38 33 17 51 23  1  7
mod 53:    3  7 31 21 33 29  2 11 32 44 20 18 38 49  4  1 21 34
mod 47:    3  7 31 33 26 13 35  2 *0 16 20 27 24  5  1 33 13  8
mod 43:    3  7 31 41 26 21  7 31 38  1  7 38 21  1 31 26  7 31
mod 41:    3  7 31  4 38 32 35 20  7 19 38 35  1  7  4 32 20  1
mod 37:    3  7 31 16 12 14 17 34  4 23 31  1 31 16 12 17  4 19
mod 31:    3  7  0  3  1  7  3 15  7 15  1  3  1  7  3  7 15  1
mod 29:    3  7  2 11 17 13 20 25  9  1  7 18 13 26 25 10  7  2
mod 23:    3  7  8 12 *0  3 17  2  1 12  5 15  2 11  7  5 15 17
mod 19:    3  7 12 13 14  2  9  1 12 14  2  1 12 13 14  9 12 13
mod 17:    3  7 14  8  7 14  1  7  8 14  8 14  1  7  8 14  7 14
mod 13:    3  7  5 10  6  1  5 10  6  5 10  1  5 10  6  5  6  1
mod 11:    3  7  9  6  1  7  6  5  7  5  1  6  1  7  6  7  5  1
mod 7:     3  0  3  1  3  1  3  1  3  3  1  1  3  1  3  3  3  1
mod 5:     3  2  1  2  2  1  1  2  2  1  2  1  1  2  2  1  2  1
mod 3:     0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

 0    - This Mersenne number is actually equal to the mod factor and is hence prime.
*0    - Prime factor; Mersenne number is composite.
Notes / Observations.

- For prime p > 2: 2p - 1 = 1 (mod 3).

- Judging by the same mod factors consistently showing up, it appears that 2p - 1 is never a multiple of 3, 5, 7, 11, 13, 17, 19 or 31 (except for situations where it is equal to them... that is, 3, 7 and 31).

- 261 - 1 (a prime number) seems to equal 1 (mod p) for a lot of primes.

- The most interesting one, in my opinion... for prime p: 2p - 1 = 1 (mod p)... or 2p = 2 (mod p) (although p > 2 for this to work). Just for comparison, it fails if p is not prime: for example. 29 - 1 = 511 = 7 (mod 9).

As I said, I wouldn't be surprised if something like this hasn't been done before already, but I figure it could make for interesting research. 2p - 1 = 1 (mod p) seems to be an interesting equality.

Last fiddled with by CuriousKit on 2015-04-06 at 03:25 Reason: Included exceptions for 3, 7 and 31.
CuriousKit is offline  
Old 2015-04-06, 03:23   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

630210 Posts
Default

I think this applies:

https://en.wikipedia.org/wiki/Hasty_generalization

Last fiddled with by retina on 2015-04-06 at 03:23
retina is offline  
Old 2015-04-06, 03:43   #3
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2·32·5 Posts
Default

I am aware that I haven't tested anywhere near enough terms to be sure. I'm just stating that this could be something that warrants further investigation towards something amounting to a proof (or a disproof). I'll need to write a specialist program (or find one) to deal with numbers greater than 264 to explore further.

I can already give an argument as to why 2p - 1 is never a multiple of 5 though... for that to be true, 2p would have to end in a 1 or a 6 (so 2p - 1 ends in a 0 or a 5). 1 is impossible on account of 2p being an even number for p > 0. For 6, it's worth noting that, starting at 21 and incrementing the index, the last digit of the result follows the cyclic pattern of 2, 4, 8, 6 and returning to 2 again. For the result to end in a 6, the index has to be a multiple of 4, and therefore is not a Mersenne prime because the exponent is not prime, so shouldn't be tested in the first place.

Other possible patterns will need a bit more thought, or a counterexample.

Last fiddled with by CuriousKit on 2015-04-06 at 03:44
CuriousKit is offline  
Old 2015-04-06, 04:54   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

231208 Posts
Default

Man, with the risk of channeling my inner RDS, you should first read some theory about modularity of those residues. If p is odd (no need to be prime) than all the factors of m=2^p-1 must be 1 or 7 (mod 8). Those mersenne numbers can't be multiples of 3,5,11,13, etc. i.e. primes which are 3 or 5 (mod 8) can't divide m. The table you show is a (very) simple consequence of chinese reminder theorem, and of the form of those numbers. Take for example 31 (this is easiest), this is a row of 5 bits in binary, so if you take every mersenne number, prime or not, which is also a row of bits, and split it in groups of 5 ones, from the right (msb), you end up at the end (left) with mostly 4 ones, which is either a 1,3,7, or 15 (mod 31).
There is no new information and no curiosity in those tables, as Retina pointed out already.
LaurV is offline  
Old 2015-04-06, 05:14   #5
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2·32·5 Posts
Default

I stand corrected. Thank you.

Apologies if all that was painfully obvious to you. I am curious of the mathematics and want to learn more.

Last fiddled with by CuriousKit on 2015-04-06 at 05:30 Reason: Never mind. Fermat's Little Theorem
CuriousKit is offline  
Old 2015-04-06, 08:23   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

6E116 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
I am curious of the mathematics and want to learn more.
That's good! One book which many people find useful is the classic "An introduction to the theory of numbers" by Hardy and Wright. The 6th edition, published in 2008 by the Oxford University Press, has ISBN 9780199219865.
Nick is offline  
Old 2015-04-06, 10:29   #7
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2·32·5 Posts
Red face

Thank you Nick. My main source of mathematical theory has been "Mathematical Methods in the Physical Sciences" by Mary L. Boas (I read Physics at Oxford), although it's currently buried in a storage box somewhere so my source of information as of late has unfortunately been Wikipedia.

Either way, it was a little embarrassing trying to effectively rediscover Fermat's Little Theorem! Hopefully the next time I post something mathematical it won't be so naïve.
CuriousKit is offline  
Old 2015-04-06, 11:39   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
I stand corrected. Thank you.

Apologies if all that was painfully obvious to you. I am curious of the mathematics and want to learn more.
An excellent viewpoint.

Try starting with:

D. Shanks Solved and Unsolved Problems in Number Theory
Hardy & Wright: Introduction to Theory of Numbers

These are just two (of many) good books on elementary number theory.

Last fiddled with by R.D. Silverman on 2015-04-06 at 11:40
R.D. Silverman is offline  
Old 2015-04-06, 11:41   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CuriousKit View Post
This has probably been done before and to a much greater depth, As I said, I wouldn't be surprised if something like this hasn't been done before already, but I figure it could make for interesting research.

.
This is like asking a baker if he has ever put his hands in a sack of flour.
R.D. Silverman is offline  
Old 2015-04-06, 11:59   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is like asking a baker if he has ever put his hands in a sack of flour.
I am still bewildered by people who are aware that they don't know anything about this subject
yet still think that they have the ability to do 'research' or somehow believe that their ideas are
'new' and worth pursuing. Especially when their ideas are nothing more than trivial pre-college level
math.

Understanding the psychology of such people eludes me.

How is it that these people think that they have anything to contribute at all?
Is it explained by Dunning & Kruger?
R.D. Silverman is offline  
Old 2015-04-06, 12:08   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
How is it that these people think that they have anything to contribute at all?
Is it explained by Dunning & Kruger?
channeling my inner RDS I can't understand that if someone is so perplexed by a problem they can't be bothered to do a quick google search: Illusory superiority is one potential explanation that came up.
science_man_88 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
exponential growth patterns MattcAnderson Puzzles 3 2015-10-04 02:33
Can You See The Patterns..? wustvn Puzzles 7 2008-11-20 14:00
Numbered Triangle: (lack of)Prime Patterns Stanek Miscellaneous Math 1 2007-08-01 14:52
Patterns SK8ER-91823 Twin Prime Search 4 2007-04-14 12:52
Something Interesting clowns789 Hardware 1 2003-12-20 12:36

All times are UTC. The time now is 11:14.


Tue Dec 7 11:14:39 UTC 2021 up 137 days, 5:43, 0 users, load averages: 1.73, 1.84, 1.61

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.