mersenneforum.org Some interesting patterns regarding mod
 Register FAQ Search Today's Posts Mark Forums Read

 2015-04-06, 03:14 #1 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 101 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: 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.
 2015-04-06, 03:23 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 11001111100012 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 101 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 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
 2015-04-06, 04:54 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 1024510 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, 05:14 #5 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 101 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
2015-04-06, 08:23   #6
Nick

Dec 2012
The Netherlands

5×353 Posts

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.

 2015-04-06, 10:29 #7 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 101 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.
2015-04-06, 11:39   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

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.

Last fiddled with by R.D. Silverman on 2015-04-06 at 11:40

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

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

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.

2015-04-06, 11:59   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

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?

2015-04-06, 12:08   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Puzzles 3 2015-10-04 02:33 wustvn Puzzles 7 2008-11-20 14:00 Stanek Miscellaneous Math 1 2007-08-01 14:52 SK8ER-91823 Twin Prime Search 4 2007-04-14 12:52 clowns789 Hardware 1 2003-12-20 12:36

All times are UTC. The time now is 05:39.

Mon Dec 5 05:39:14 UTC 2022 up 109 days, 3:07, 0 users, load averages: 0.60, 0.82, 0.95