20210104, 22:53  #1 
Sep 2002
Database er0rr
2^{2}×13×71 Posts 
crazy Mersenne test
If there exists a nonpower of 2, k, such that Mod(k,n)^p==1 then n, a Mersenne number, is composite. E.g.
Is there any quick way to identify a k for a particular n? MODERATOR NOTE: I assumed n = 2^p  1, and verified that Mod(39, 2047)^11 == 1 and Mod(156171,8388607)^23 == 1. Last fiddled with by Dr Sardonicus on 20210105 at 00:02 Reason: Notational oopsadaisy 
20210105, 00:25  #2 
Feb 2017
Nowhere
11E5_{16} Posts 
If n = 2^p  1 is composite, there are k which are not powers of 2, such that Mod(k,n)^p ==1.
If n = q*d, we can take i and j from 1 to p1, with i<> j, and k = chinese(Mod(2^i,q),Mod(2^j,d)) There are (p1)*(p2) such pairs (i,j). So for 2^11  1 = 23*89, there are 10*9 = 90 values of k. If n = 2^p  1 has f > 2 prime factors, the number of k is equal to the number of ftuples of integers from 1 to p1, not all of which are equal. 
20210105, 00:31  #3 
Sep 2002
Database er0rr
2^{2}·13·71 Posts 
Counting the number of all solutions (including powers of 2) for p=11, 23, 29 seems to indicate that this count is equal to p^{#factors}.
Last fiddled with by paulunderwood on 20210105 at 00:36 
20210105, 00:49  #4  
Feb 2017
Nowhere
3^{2}·509 Posts 
Quote:
I note that my count of nonpowers of 2 was wrong. I failed to notice that you can take tuples of integers from 0 to p1 as exponents (not 1 to p1). So for 2 prime factors you get p*(p1) nonpowers of 2, and p powers of 2, one of which is 1. ^{†}If 2^p  1 is divisible by q^m for m > 1, you use the group of order p generated by Mod(2, q^m). AFAIK not a single example of such a q is known for p prime, but there is no proof that none exists. Last fiddled with by Dr Sardonicus on 20210105 at 00:50 

20210105, 01:00  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,019 Posts 
Not sure if it is of any value but regardless to State the obvious:
Mod(39, 2047)^11 == 1 Is another way of saying (2^111)  39^111 Now if I am not mistaking 391  39^111 The candidate k's could be brute forced As (k1)*(2^n1)*c Choosing large k's should yield fastest results. Haven't verified if this is generally the case. Just my 2 cents which is worth less than 3 pence. Last fiddled with by a1call on 20210105 at 01:01 
20210105, 01:51  #6  
"Viliam Furík"
Jul 2018
Martin, Slovakia
3·5^{2}·7 Posts 
Quote:
This should be exactly all of them. Code:
39 93 105 121 167 179 223 269 271 331 357 395 423 449 453 461 509 535 579 601 625 627 639 809 817 929 995 1043 1107 1113 1135 1159 1189 1221 1235 1291 1313 1337 1343 1521 1545 1577 1591 1603 1641 1669 1695 1819 1825 1871 1933 1959 2003 2025 Did I misunderstand the value of 90? 

20210105, 01:58  #7 
Mar 2016
5·67 Posts 
I get other values and you could visualize them:
http://devalco.de/System/system_natural.php?prim=2047 
20210105, 02:06  #8 
"Viliam Furík"
Jul 2018
Martin, Slovakia
3×5^{2}×7 Posts 
I have found, that for p = 23, there is a smaller k, specifically 83663.

20210105, 02:25  #9  
Feb 2017
Nowhere
3^{2}×509 Posts 
Quote:
I wrote a mindless script to calculate the nontwopower k < 2^11  1: Code:
? v=vector(110);k=0;for(i=0,10,for(j=0,10,if(i<>j,k++;v[k]=lift(chinese(Mod(2,23)^i,Mod(2,89)^j))))) ? print(vecsort(v)) [39, 78, 93, 105, 121, 156, 167, 179, 186, 210, 223, 242, 269, 271, 312, 331, 334, 357, 358, 372, 395, 420, 423, 446, 449, 453, 461, 484, 509, 535, 538, 542, 579, 601, 624, 625, 627, 639, 662, 668, 714, 716, 744, 790, 809, 817, 840, 846, 892, 898, 906, 922, 929, 968, 995, 1018, 1043, 1070, 1076, 1084, 1107, 1113, 1135, 1158, 1159, 1189, 1202, 1221, 1235, 1248, 1250, 1254, 1278, 1291, 1313, 1324, 1336, 1337, 1343, 1428, 1432, 1488, 1521, 1545, 1577, 1580, 1591, 1603, 1618, 1634, 1641, 1669, 1680, 1692, 1695, 1784, 1796, 1812, 1819, 1825, 1844, 1858, 1871, 1933, 1936, 1959, 1990, 2003, 2025, 2036] 

20210105, 02:41  #10 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·2,381 Posts 
Isn't this the same like discrete logarithm? The "^11" (i.e. "^p") has not much to do there, any power can be used. If 2 is used, we are getting to the problem of finding the square root of 1 (mod m). Ex, for p=11, m=2^p+1, we have \(\pm 622\) as one of the roots (\(622^2=1\) (mod 2047)). A prime m will have only 2 roots (+1 and 1 (mod m)), while a composite m will have more roots depending on the number of factors.
Now, if you can do that, you can also factor m (because in this case (r1)(r+1)=0 (mod m) and you take the gcd with one of them, i.e. gcd(621,2047)=23, gcd(623,2047)=89). Using the 11th power is the same, except it is longer and a bit more complicate Last fiddled with by LaurV on 20210105 at 02:42 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Crazy spike in LL tests submitted  Uncwilly  PrimeNet  19  20190411 19:13 
New Mersenne Software For Test Mersenne Prime Numbers On Android  thorken  Software  66  20190113 21:08 
Crazy question...  guido72  Software  6  20080816 02:34 
My Prime95 is going crazy!!  xago666  Information & Answers  2  20080312 18:38 
crazy WinXP scheduling  stippix  Software  0  20040422 08:55 