20150406, 03:14  #1 
"J. Gareth Moreton"
Feb 2015
Nomadic
2×3^{2}×5 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.  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^{61}  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^{9}  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 20150406 at 03:25 Reason: Included exceptions for 3, 7 and 31. 
20150406, 03:23  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6302_{10} Posts 
Last fiddled with by retina on 20150406 at 03:23 
20150406, 03:43  #3 
"J. Gareth Moreton"
Feb 2015
Nomadic
2·3^{2}·5 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^{64} 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^{1} 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 20150406 at 03:44 
20150406, 04:54  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23120_{8} 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^p1 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. 
20150406, 05:14  #5 
"J. Gareth Moreton"
Feb 2015
Nomadic
2·3^{2}·5 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 20150406 at 05:30 Reason: Never mind. Fermat's Little Theorem 
20150406, 08:23  #6 
Dec 2012
The Netherlands
6E1_{16} Posts 
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.

20150406, 10:29  #7 
"J. Gareth Moreton"
Feb 2015
Nomadic
2·3^{2}·5 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. 
20150406, 11:39  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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 20150406 at 11:40 

20150406, 11:41  #9 
Nov 2003
2^{2}·5·373 Posts 
This is like asking a baker if he has ever put his hands in a sack of flour.

20150406, 11:59  #10  
Nov 2003
7460_{10} Posts 
Quote:
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 precollege 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? 

20150406, 12:08  #11  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
exponential growth patterns  MattcAnderson  Puzzles  3  20151004 02:33 
Can You See The Patterns..?  wustvn  Puzzles  7  20081120 14:00 
Numbered Triangle: (lack of)Prime Patterns  Stanek  Miscellaneous Math  1  20070801 14:52 
Patterns  SK8ER91823  Twin Prime Search  4  20070414 12:52 
Something Interesting  clowns789  Hardware  1  20031220 12:36 