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

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.

[CODE] 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))))[/CODE]

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

[QUOTE=charybdis;610957]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 [URL="https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/plms/s2-9.1.244"]Western (1911) proved[/URL], 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".[/QUOTE]Thank you very much for digging up a pertinent reference on when 2 is an 8[sup]th[/sup] 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, [i]much[/i] 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, [i]which[/i] quarter is not predictable using linear congruences.

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

[b]EDIT:[/b] I checked it myself for p < 10[sup]8[/sup], with the results following:
[code]? 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[/code]

[QUOTE=charybdis;610957]This is equivalent to...[/QUOTE]
Very :goodposting: :tu:

[QUOTE=kijinSeija;610959]Ok thanks for your answer I understand a little more now. :grin:

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>[/QUOTE]Reread the explanatory post by [b][color=blue]charybdis[/color][/b]. 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.

A repetitive pattern in observed after [I]k[/I] = 12 for the primes [I]p[/I] and the values of [I]k[/I] for which primes 2[I]kp[/I] + 1 can be found that divide the Mersenne numbers 2[I][SUP]p[/SUP][/I] - 1,
see the previous posts #29 and #30 at [URL]https://www.mersenneforum.org/showpost.php?p=606844&postcount=29[/URL] and [URL]https://www.mersenneforum.org/showpost.php?p=607412&postcount=30[/URL].

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

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

It seems that the primes of the forms

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

cannot be factors of M[M]1277[/M].

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

[QUOTE=Dobri;611207]A repetitive pattern in observed after [I]k[/I] = 12 for the primes [I]p[/I] and the values of [I]k[/I] for which primes 2[I]kp[/I] + 1 can be found that divide the Mersenne numbers 2[I][SUP]p[/SUP][/I] - 1,
see the previous posts #29 and #30 at [URL]https://www.mersenneforum.org/showpost.php?p=606844&postcount=29[/URL] and [URL]https://www.mersenneforum.org/showpost.php?p=607412&postcount=30[/URL].

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

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

It seems that the primes of the forms

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

cannot be factors of M[M]1277[/M].[/QUOTE]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.

[QUOTE=Dobri;611207]

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

[/QUOTE]




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

[QUOTE=User140242;611220]
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
[/QUOTE]
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...
:party:

[QUOTE=LaurV;611260]

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

[/QUOTE]
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:


[QUOTE]

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[/QUOTE]
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.

[QUOTE=User140242;611263]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.[/QUOTE]

[QUOTE=LaurV;611260](You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)).
[/QUOTE]

Bingo!

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