mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Dobri

Reply
 
Thread Tools
Old 2022-08-08, 12:10   #34
kijinSeija
 
Mar 2021
France

41 Posts
Default

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.
kijinSeija is offline   Reply With Quote
Old 2022-08-08, 14:32   #35
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×1,993 Posts
Default

Quote:
Originally Posted by charybdis View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-09, 01:39   #36
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

1010510 Posts
Default

Quote:
Originally Posted by charybdis View Post
This is equivalent to...
Very
LaurV is offline   Reply With Quote
Old 2022-08-09, 13:17   #37
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

135338 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-11, 11:10   #38
Dobri
 
"Καλός"
May 2018

3·112 Posts
Default

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.
Dobri is offline   Reply With Quote
Old 2022-08-11, 13:16   #39
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

235718 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2022-08-11, 13:19   #40
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

175B16 Posts
Default

Quote:
Originally Posted by Dobri View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-11, 13:58   #41
User140242
 
Jul 2022

2·52 Posts
Default

Quote:
Originally Posted by Dobri View Post

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
User140242 is offline   Reply With Quote
Old 2022-08-12, 07:43   #42
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

5×43×47 Posts
Default

Quote:
Originally Posted by User140242 View Post
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
LaurV is offline   Reply With Quote
Old 2022-08-12, 08:08   #43
User140242
 
Jul 2022

2×52 Posts
Default

Quote:
Originally Posted by LaurV View Post

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.
User140242 is offline   Reply With Quote
Old 2022-08-12, 08:15   #44
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100111011110012 Posts
Default

Quote:
Originally Posted by User140242 View Post
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 View Post
(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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Repeating residues in LL tests of composite Mersenne numbers Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45
Mersenne number with exponent 333333367 is composite TheGuardian GPU Computing 25 2019-05-09 21:53
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 10:15.


Wed Sep 28 10:15:16 UTC 2022 up 41 days, 7:43, 0 users, load averages: 0.57, 0.80, 0.90

Powered by vBulletin® Version 3.8.11
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.

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