crazy Mersenne test

[paulunderwood]

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.

[Dr Sardonicus]

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.

[paulunderwood]

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}.

[Dr Sardonicus]

Originally Posted by paulunderwood

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.

[a1call]

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.

[Viliam Furik]

Originally Posted by Dr Sardonicus

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.

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?

[bhelmes]

I get other values and you could visualize them:
http://devalco.de/System/system_natural.php?prim=2047

[Viliam Furik]

I have found, that for p = 23, there is a smaller k, specifically 83663.

[Dr Sardonicus]

Originally Posted by Viliam Furik

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:

? 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]

[LaurV]

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