Mersenne Numbers Known from Number Practice to Be Composite

[kijinSeija]

Ok thanks for your answer I understand a little more now.

Do you think you can prove the same thing about Wagstaff composite numbers ?

I found than if 8p+1 = 256a^2+(2*b-1)^2 and p and 8p+1 is prime, then 8p+1 divides (2^p+1)/3.

 cnt=0; for(b=1, 1000, for(a=1, 1000, q=256*(a)^2+(2*b-1)^2;  p=(q-1)/8; if(isprime(p)&&isprime(q), cnt++; print(cnt": "q", "p))))

So I think the proof the same with some minor change.

[Dr Sardonicus]

Originally Posted by charybdis

This is equivalent to saying that if 8p+1 is prime and of the form (2a-1)^2+64(2b-1)^2, then 2 is an 8th power mod 8p+1.

You've rediscovered an old result on when 2 is an 8th power modulo a prime. Reuschle (1856) stated, and Western (1911) proved, that if q is a prime of the form 8k+1:
- If k is even, then 2 is an 8th power mod q if and only if q is of the form x^2 + 256y^2
- If k is odd, then 2 is an 8th power mod q if and only if q is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2.

Here we are in the k odd case, and your (2a-1)^2+64(2b-1)^2 exactly corresponds to saying that 8p+1 is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2. So in fact we can strengthen your statement to an "if and only if".

Thank you very much for digging up a pertinent reference on when 2 is an 8^th power (mod q) when q is congruent to 1 (mod 8).

An even older result is the criterion for when 2 is a biquadratic (fourth power) residue (mod q); namely, when

q = x^2 + 64*y^2 (x, y positive integers).

As already indicated, however, it is much, much quicker to determine whether q = 8*p + 1 divides 2^p - 1 by modulo arithmetic, than it is to determine whether q is of the appropriate quadratic form.

I would expect that q = 8*p + 1 divides 2^p - 1 for about a quarter of the primes p for which q = 8*p + 1 is prime. Unfortunately, which quarter is not predictable using linear congruences.

I don't necessarily trust my thinking here, so someone may want to check on the proportion...

EDIT: I checked it myself for p < 10⁸, with the results following:

? c1=0;c2=0;forprime(p=3,100000000,q=8*p+1;if(ispseudoprime(q),c1++;if(Mod(2,q)^p-1==0,c2++)));print(c1" "c2" "1.*c2/c1)

392989 98264 0.25004262205812376427838947146103326047

[LaurV]

Originally Posted by charybdis

This is equivalent to...

Very

[Dr Sardonicus]

Originally Posted by kijinSeija

Ok thanks for your answer I understand a little more now.

Do you think you can prove the same thing about Wagstaff composite numbers ?

I found than if 8p+1 = 256a^2+(2*b-1)^2 and p and 8p+1 is prime, then 8p+1 divides (2^p+1)/3.
<snip>

Reread the explanatory post by charybdis. Also note the result I mentioned about when 2 is a fourth power residue (mod q). The result you state is an easy consequence of your hypothesis and those results.

[Dobri]

A repetitive pattern in observed after k = 12 for the primes p and the values of k for which primes 2kp + 1 can be found that divide the Mersenne numbers 2^p - 1,
see the previous posts #29 and #30 at https://www.mersenneforum.org/showpo...4&postcount=29 and https://www.mersenneforum.org/showpo...2&postcount=30.

For example, for p = 1277 (where p mod 4 = 1 and p mod 6 = 5), possible prime factors that divide M1277 have to be of the following forms (note that 3 + 4 = 7 and 3 × 4 = 12):

2(12m+3)p + 1,
2(12m+4)p + 1,
2(12m+7)p + 1, and
2(12(m+1))p + 1, m = 0, 1, 2,...

It seems that the primes of the forms

2(12m+1)p + 1,
2(12m+5)p + 1,
2(12m+8)p + 1,
2(12m+9)p + 1, and
2(12m+11)p + 1, m = 0, 1, 2,...,

cannot be factors of M1277.

[LaurV]

Can you also work this stuff (mod 4620) ?
Or, start with (mod 420) first...

[Dr Sardonicus]

Originally Posted by Dobri

A repetitive pattern in observed after k = 12 for the primes p and the values of k for which primes 2kp + 1 can be found that divide the Mersenne numbers 2^p - 1,
see the previous posts #29 and #30 at https://www.mersenneforum.org/showpo...4&postcount=29 and https://www.mersenneforum.org/showpo...2&postcount=30.

For example, for p = 1277 (where p mod 4 = 1 and p mod 6 = 5), possible prime factors that divide M1277 have to be of the following forms (note that 3 + 4 = 7 and 3 × 4 = 12):

2(12m+3)p + 1,
2(12m+4)p + 1,
2(12m+7)p + 1, and
2(12(m+1))p + 1, m = 0, 1, 2,...

It seems that the primes of the forms

2(12m+1)p + 1,
2(12m+5)p + 1,
2(12m+8)p + 1,
2(12m+9)p + 1, and
2(12m+11)p + 1, m = 0, 1, 2,...,

cannot be factors of M1277.

For odd p we have (2^((p+1)/2))^2 == 2 (mod q) for every prime factor q of 2^p - 1, so 2 is a quadratic residue (mod q). As is well known, this means that q == 1 or 7 (mod 8).

It is also well known that if p is an odd prime, and q divides 2^p - 1, then q = 2*k*p + 1 for some positive integer k. If p == 1 (mod 4) we then have 2*k*p + 1 == 2*k + 1 == 1 or 7 (mod 8). Thus, k == 0 or 3 (mod 4).

For p == 1 (mod 4), this automatically rules out q = 2*k*p + 1 for k = 12*m + 1, 12*m + 5, or 12*m + 9 since 2*k*p + 1 == 3 (mod 8) for such k.

[User140242]

Originally Posted by Dobri

2(12m+3)p + 1,
2(12m+4)p + 1,
2(12m+7)p + 1, and
2(12(m+1))p + 1, m = 0, 1, 2,...

I found this from an empirical observation but I think it is easy to prove that taking a prime number p

we have (2^p - 1)=7 (mod 8) or also

(2^p - 1)=1+2*p+8*p*k if p%4==3 , where % is the modulo operator

or (2^p - 1)=1+6*p+8*p*k if p%4==1


and if (2^p - 1)=N1*N2 then N1=1 (mod 8) and N2=7 (mod 8) but also N1=1 (mod 2*p) and N2=1 (mod 2*p)

then the only possible solution to find possible factors is this

N1=1+8*p*k1 and

N2=1+2*p+8*p*k2 if p%4==3 or N2=1+6*p+8*p*k2 if p%4==1

so if we exclude multiples of 3 for m>=0

N1=1+24*p*(m+1) or 1+16*p+24*p*m if p%6=1
N1=1+24*p*(m+1) or 1+ 8*p+24*p*m if p%6=5

and

N2=1+10*p+24*p*m or 1+18*p+24*p*m if p%6=1 and p%4==3
N2=1+ 2*p+24*p*m or 1+18*p+24*p*m if p%6=5 and p%4==3



or



N2=1+6*p+24*p*m or 1+22*p+24*p*m if p%6=1 and p%4==1
N2=1+6*p+24*p*m or 1+14*p+24*p*m if p%6=5 and p%4==1

[LaurV]

Originally Posted by User140242

then the only possible solution to find possible factors is this
N1=1+8*p*k1 and
N2=1+2*p+8*p*k2 if p%4==3 or N2=1+6*p+8*p*k2 if p%4==1

OK, perfect, using the standard notation, where the factors q of m=2^p-1 are of the form q=2kp+1, and in the same time they are either 1 or -1 (mod 8), you just found the classes of k, depending on the classes of p, (mod 4).
As p is prime, it can only be 1 or 3 (mod 4), because it can not be even.
1. if p=1 (mod 4), then k can only be 0 or 3 (mod 4).
2. if p=3 (mod 4), then k can only be 0 or 1 (mod 4).

Now stop here, the other stuff (mod 6, etc.) is not useful, as it doesn't reduce the searching space.

Next step is to put 3 into equation, and find the classes of k, depending on the classes of p (mod 12).
As p is prime, it can only be 1, 5, 7, or 11 (mod 12).
What are the classes of k, in each case?
1. when p=1 (mod 12), k can only be ??? (mod 12)
2. when p=5 (mod 12), k can only be ??? (mod 12)
3. when p=7 (mod 12), k can only be ??? (mod 12)
4. when p=11 (mod 12), k can only be ??? (mod 12)
Fill in the question marks. (You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)).

Next step is to put 5 into equation, and find the classes of k, depending on the classes of p (mod 60).
There are 16 classes of p (mod 60).

Next step is to put 7 into equation, and find the classes of k, depending on the classes of p (mod 420).
That is what (and why) I was asking you to do, in my previous post.
There are 96 classes of p (mod 420).

To find more about these numbers, and where do they come from, you can read about Euler's Phy function.

Next step is to put 11 into equation, and find the classes of k, depending on the classes of p (mod 4620).
There are 960 classes of p (mod 4620).

If you succeed to reach this point, congratulations, you just discovered how mfaktc and its relatives work...

[User140242]

Originally Posted by LaurV

Now stop here, the other stuff (mod 6, etc.) is not useful, as it doesn't reduce the searching space.

If you use the result in a wheel sieve with a bW basis, you can call classes or possible remainders (modulo bW).

If a basis bW=8*p is used, the possible factors are of the type q = 1+8*k*p and q=1+2*p+8*k*p if p%4==3 or q=1+6*p+8*k*p if p%4==1.
so there are 2 classes or possible remainders [1 , 1+2*p] if p%4==3 or [1 , 1+6*p] if p%4==1.

If a basis bW=24*p is used as mentioned above, the possible factors are:

N1=1+24*p*(m+1) or 1+16*p+24*p*m if p%6=1
N1=1+24*p*(m+1) or 1+ 8*p+24*p*m if p%6=5

and

N2=1+10*p+24*p*m or 1+18*p+24*p*m if p%6=1 and p%4==3
N2=1+ 2*p+24*p*m or 1+18*p+24*p*m if p%6=5 and p%4==3

or

N2=1+6*p+24*p*m or 1+22*p+24*p*m if p%6=1 and p%4==1
N2=1+6*p+24*p*m or 1+14*p+24*p*m if p%6=5 and p%4==1

so there are 4 possible classes or remainders based on the value of p%4 and p%6 in fact combining the results of p%4 and p%6 is the same as evaluating p%12.

[LaurV]

Originally Posted by User140242

so there are 4 possible classes or remainders based on the value of p%4 and p%6 in fact combining the results of p%4 and p%6 is the same as evaluating p%12.

Originally Posted by LaurV

(You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)).

Bingo!

You still get 4 classes to test for factors; to reduce more the percentages, you need new primes in the modulo.