mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-01-04, 22:53   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

70058 Posts
Default crazy Mersenne test

If there exists a non-power of 2, k, such that Mod(k,n)^p==1 then n, a Mersenne number, is composite. E.g. n p=11, k=39; n p=23, k=156171.

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 2021-01-05 at 00:02 Reason: Notational oopsadaisy
paulunderwood is offline   Reply With Quote
Old 2021-01-05, 00:25   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10DA16 Posts
Default

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 p-1, with i<> j, and

k = chinese(Mod(2^i,q),Mod(2^j,d))

There are (p-1)*(p-2) 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 f-tuples of integers from 1 to p-1, not all of which are equal.
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-05, 00:31   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110000001012 Posts
Default

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 2021-01-05 at 00:36
paulunderwood is offline   Reply With Quote
Old 2021-01-05, 00:49   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×719 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Counting the number of all solutions (including powers of 2) for p=11, 23, 29 seems to indicate that thus count is equal to p^{#factors}.
That would be correct. For each prime factor q of 2^p - 1, the group of elements of order p (mod q) is cyclic of order p, and is generated by Mod(2, q). So the group of elements of order p (mod 2^p - 1) is the direct product of #primefactors cyclic groups of order p.

I note that my count of non-powers of 2 was wrong. I failed to notice that you can take tuples of integers from 0 to p-1 as exponents (not 1 to p-1). So for 2 prime factors you get p*(p-1) non-powers 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 2021-01-05 at 00:50
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-05, 01:00   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7C016 Posts
Default

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^11-1) | 39^11-1
Now if I am not mistaking
39-1 | 39^11-1
The candidate k's could be brute forced
As
(k-1)*(2^n-1)*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 2021-01-05 at 01:01
a1call is offline   Reply With Quote
Old 2021-01-05, 01:51   #6
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

373 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
There are (p-1)*(p-2) such pairs (i,j). So for 2^11 - 1 = 23*89, there are 10*9 = 90 values of k.
I have calculated 110 (11 * 10) non-2-power-values of k, under 2047. A big chunk of them were power-of-2 multiples of the smaller odd k's. Ignoring those, the number is 54.

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
There also seems to be a lot more (if not infinitely many) of the odd k's above 2047.

Did I misunderstand the value of 90?
Viliam Furik is offline   Reply With Quote
Old 2021-01-05, 01:58   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

24×19 Posts
Default

I get other values and you could visualize them:
http://devalco.de/System/system_natural.php?prim=2047
bhelmes is offline   Reply With Quote
Old 2021-01-05, 02:06   #8
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

373 Posts
Default

I have found, that for p = 23, there is a smaller k, specifically 83663.
Viliam Furik is offline   Reply With Quote
Old 2021-01-05, 02:25   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×719 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
I have calculated 110 (11 * 10) non-2-power-values of k, under 2047.
<snip>
Did I misunderstand the value of 90?
No. I screwed up. I should have allowed the exponent of 2 to run from 0 to 10, not 1 to 10 as I originally did.
I wrote a mindless script to calculate the non-two-power 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]
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-05, 02:41   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·17·109 Posts
Default

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 (r-1)(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 2021-01-05 at 02:42
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Crazy spike in LL tests submitted Uncwilly PrimeNet 19 2019-04-11 19:13
New Mersenne Software For Test Mersenne Prime Numbers On Android thorken Software 66 2019-01-13 21:08
Crazy question... guido72 Software 6 2008-08-16 02:34
My Prime95 is going crazy!! xago666 Information & Answers 2 2008-03-12 18:38
crazy WinXP scheduling stippix Software 0 2004-04-22 08:55

All times are UTC. The time now is 17:16.

Thu Feb 25 17:16:05 UTC 2021 up 84 days, 13:27, 0 users, load averages: 1.98, 1.93, 1.92

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.