 mersenneforum.org Mersenne Numbers Known from Number Practice to Be Composite
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2022-08-08, 12:10 #34 kijinSeija   Mar 2021 France 41 Posts 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. 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)))) So I think the proof the same with some minor change.   2022-08-08, 14:32   #35
Dr Sardonicus

Feb 2017
Nowhere

13·461 Posts Quote:
 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 8th 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 < 108, 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

Last fiddled with by Dr Sardonicus on 2022-08-08 at 23:02 Reason: As indicated   2022-08-09, 01:39   #36
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×3×211 Posts Quote:
 Originally Posted by charybdis This is equivalent to...
Very     2022-08-09, 13:17   #37
Dr Sardonicus

Feb 2017
Nowhere

135518 Posts Quote:
 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.
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.   2022-08-11, 11:10 #38 Dobri   "Καλός" May 2018 5×73 Posts 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 2p - 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.   2022-08-11, 13:16 #39 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 24·3·211 Posts Can you also work this stuff (mod 4620) ? Or, start with (mod 420) first... Last fiddled with by LaurV on 2022-08-11 at 13:16   2022-08-11, 13:19   #40
Dr Sardonicus

Feb 2017
Nowhere

13·461 Posts Quote:
 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 2p - 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.   2022-08-11, 13:58   #41
User140242

Jul 2022

22·13 Posts Quote:
 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

Last fiddled with by User140242 on 2022-08-11 at 14:52   2022-08-12, 07:43   #42
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×3×211 Posts Quote:
 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... Last fiddled with by LaurV on 2022-08-12 at 08:03   2022-08-12, 08:08   #43
User140242

Jul 2022

22×13 Posts Quote:
 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:

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
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.   2022-08-12, 08:15   #44
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·3·211 Posts Quote:
 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.
Quote:
 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.

Last fiddled with by LaurV on 2022-08-12 at 09:07   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45 TheGuardian GPU Computing 25 2019-05-09 21:53 jshort Factoring 9 2019-04-09 16:34 wildrabbitt Math 120 2016-09-29 21:52 philmoore Factoring 21 2004-11-18 20:00

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

Tue Oct 4 09:16:33 UTC 2022 up 47 days, 6:45, 0 users, load averages: 1.01, 1.01, 1.18

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔