Some interesting patterns regarding mod

CuriousKit · 2015-04-06, 03:14

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: 2^p - 1 = 1 (mod 3).

- Judging by the same mod factors consistently showing up, it appears that 2^p - 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).

- 2⁶¹ - 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: 2^p - 1 = 1 (mod p)... or 2^p = 2 (mod p) (although p > 2 for this to work). Just for comparison, it fails if p is not prime: for example. 2⁹ - 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. 2^p - 1 = 1 (mod p) seems to be an interesting equality.

retina · 2015-04-06, 03:23

I think this applies:

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

CuriousKit · 2015-04-06, 03:43

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 2⁶⁴ to explore further.

I can already give an argument as to why 2^p - 1 is never a multiple of 5 though... for that to be true, 2^p would have to end in a 1 or a 6 (so 2^p - 1 ends in a 0 or a 5). 1 is impossible on account of 2^p being an even number for p > 0. For 6, it's worth noting that, starting at 2¹ 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.

LaurV · 2015-04-06, 04:54

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.

CuriousKit · 2015-04-06, 05:14

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.

Nick · 2015-04-06, 08:23

Quote:

Originally Posted by CuriousKit

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.

CuriousKit · 2015-04-06, 10:29

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.

R.D. Silverman · 2015-04-06, 11:39

Quote:

Originally Posted by CuriousKit

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.

R.D. Silverman · 2015-04-06, 11:41

Quote:

Originally Posted by CuriousKit

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 · 2015-04-06, 11:59

Quote:

Originally Posted by R.D. Silverman

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?

science_man_88 · 2015-04-06, 12:08

Quote:

Originally Posted by R.D. Silverman

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.

2015-04-06, 03:14	#1
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 69₁₆ Posts	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: 2^p - 1 = 1 (mod* 3). - Judging by the same mod factors consistently showing up, it appears that 2^p - 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). - 2⁶¹ - 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: 2^p - 1 = 1 (mod p)... or 2^p = 2 (mod p) (although p > 2 for this to work). Just for comparison, it fails if p is not prime: for example. 2⁹ - 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. 2^p - 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.

2015-04-06, 03:23	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2·3²·7·53 Posts	I think this applies: https://en.wikipedia.org/wiki/Hasty_generalization Last fiddled with by retina on 2015-04-06 at 03:23

2015-04-06, 03:43	#3
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 3×5×7 Posts	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 2⁶⁴ to explore further. I can already give an argument as to why 2^p - 1 is never a multiple of 5 though... for that to be true, 2^p would have to end in a 1 or a 6 (so 2^p - 1 ends in a 0 or a 5). 1 is impossible on account of 2^p being an even number for p > 0. For 6, it's worth noting that, starting at 2¹ 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

2015-04-06, 05:14	#5
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 3×5×7 Posts	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

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

2015-04-06, 04:54	#4
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 10,273 Posts	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.

2015-04-06, 10:29	#7
CuriousKit "J. Gareth Moreton" Feb 2015 Nomadic 3·5·7 Posts	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.