20121207, 07:43  #23  
Romulan Interpreter
Jun 2011
Thailand
2^{2}·3·739 Posts 
Quote:
So, one can modify the forstep parameters to go as high as he likes, eventually going 4 by 4 to be faster, and/or cancelling 5+12i test (I use the step 2 by 2 and testing both cases to show that the thing is working, you can also remove the primality test and it will print primes, or use ispseudoprime(n,1) to make it much faster, but here be careful that you can lose solutions if the random base for RM test is unlucky selected). Code:
gp > nr=0; cnt=0; forstep(n=11,10^7,2,if(((z=(Mod(3,n)+Mod(2,n)*I)^(n+1))==13z==5+12*I)&&!isprime(n),nr++; print(n" : "n%4" ")); if(n >cnt,cnt+=10^6; printf("...%d...%c",n,13))); nr 1105 : 1 2465 : 1 10585 : 1 29341 : 1 ...<snip many lines deleted>... 9131401 : 1 9638785 : 1 9890881 : 1 %6 = 69 gp > 

20121207, 11:45  #24 
(loop (#_fork))
Feb 2006
Cambridge, England
1100010110010_{2} Posts 
random thoughts comprised entirely of inutility
My suspicion is that the '==3 mod 4' part means that counterexamples are large because they have to be a product of three primes ==3 mod 4.
Looking at the way that pseudoprimes work in base 2: Code:
for k in [1000000..2000000] do b:=IntegerRing(k)!2; t:=b^k; if (t eq 2 and not IsPrime(k)) then print k, Factorisation(k); for j in PrimeDivisors(k) do print " ",j,Order(FiniteField(j)!2); end for; end if; end for; what happens if you look at products of three primescongruentto3mod4 where (3+2i) has small order mod each p_i? Code:
TT:=[]; S:=1; for t in [1..200000] do S:=4+S; while (not IsPrime(S)) do S:=4+S; end while; Q:=FiniteField(S^2); QQ:=S^21; i:=Sqrt(Q!1); if (Order(3+2*i) lt 30*QQ/S) then print S,QQ/Order(3+2*i),Factorisation(Order(3+2*i)); Append(~TT,S); end if; end for; print TT; P<x>:=PolynomialRing(Integers()); print "begin"; for a in TT do for b in TT do for c in TT do if (a gt b and b gt c) then So:=a*b*c; S:=IntegerRing(So); Sx<x>:=PolynomialRing(S); Sx1<q>:=quo<Sxx^2+1>; k:=Coefficient((3+2*q)^So,0); if (k lt 10000 or k gt So10000) then print a,b,c,So, k; end if; end if; end for; end for; end for; print "end"; 
20121207, 12:00  #25 
(loop (#_fork))
Feb 2006
Cambridge, England
1100010110010_{2} Posts 
hmm, this is possibly quite an interesting additional question:
How big a set of 4k+3primes can you find where 3+2i has the same order mod each prime? How about the same oddpartoforder? The birthday paradox isn't really on our side because the orders are aroundp^2 rather than aroundp. think of something like 1011863 990288 23 [ <47, 1>, <21529, 1> ] 47 23 43994 43056 21529 23 43994 43056 1012441 1008000 120 [ <241, 1>, <4201, 1> ] 241 120 8437 8400 4201 120 8437 8400 base53 pseudoprimes the top lines are N, phi(N), order of 53 mod N, factorisation of N the indented lines are p, O=order of 53 mod p, (N1)/O, phi(N)/O so having two primes where 53 has the same order was at least a good start 
20121207, 16:01  #26 
(loop (#_fork))
Feb 2006
Cambridge, England
2×29×109 Posts 
... ok, so the numbers where the order of 2 mod p is 47 are 2351 and 4513, which are among the factors of 2^471.
So maybe we want to be looking at the factorisation into primes of Z[i] of (3+2*i)^k1. But, hmm, it looks as if the norms of such numbers with k prime only have prime factors which are congruent to 1 mod 4 ... so we're getting 'accidental' factors for composite k, and they're a lot rarer and a lot smaller. Last fiddled with by fivemack on 20121212 at 14:48 
20121208, 11:22  #27 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×3×739 Posts 
There are no counterexample 3 (mod 4) for b=3+2i, up to n=10^10 (and a bit upper).
I stoped it. 
20121210, 02:45  #28 
Dec 2012
China
11_{10} Posts 
how to prove has no Positive integer root, is variable , is constant and are parameter
,and all character represents Positive integer.it's a question about the conjecture. my proof on mathoverflow : http://mathoverflow.net/questions/11...eseconditions Last fiddled with by wsc812 on 20121210 at 02:54 
20121210, 18:45  #29 
Nov 2012
Bonn University
2^{3} Posts 
Pomerance's reasoning for BPSW works here as well
I think Alex Kruppa is correct about this being essentially a combination of a (p1) and a (p+1)test. Moreover, the examples (if any) constructed by C. Pomerance's heuristic are all expamples of pseudoprimes for the test considered in this thread.

20121211, 02:51  #30  
Bemusing Prompter
"Danny"
Dec 2002
California
2308_{10} Posts 
Quote:


20121211, 09:16  #31 
"Nancy"
Aug 2002
Alexandria
2^{5}×7×11 Posts 
Welcome on mersenneforum, Jens!

20121213, 10:18  #32 
Dec 2012
China
11 Posts 
I have found the
Complete proof for N=4k+3!!!!! 
20121213, 13:32  #33 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
21031_{8} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test  a1call  Miscellaneous Math  194  20180319 05:54 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
Testing Mersenne cofactors for primality?  CRGreathouse  Computer Science & Computational Number Theory  18  20130608 19:12 
a new primality testing method  jasong  Math  1  20071106 21:46 