Complex Prime Number Test
11-11-2014, 06:09 PM (This post was last modified: 11-13-2014 01:21 PM by Eddie W. Shore.)
Post: #1
 Eddie W. Shore Senior Member Posts: 975 Joined: Dec 2013
Complex Prime Number Test
Program:
Code:
EXPORT cisprime(z) BEGIN // 2014-11-09 EWS LOCAL a,b,r,t; a:=RE(z); b:=IM(z); r:=a^2+b^2; IF CAS.isPrime(r)==1 THEN t:=1; END; IF a==0 AND ABS(b) MOD 4==3 AND CAS.isprime(ABS(b))==1 THEN t:=1; END; IF b==0 AND ABS(a) MOD 4==3 AND CAS.isprime(ABS(a))==1 THEN t:=1; END; RETURN t; END;
(Edited 2014-11-13, see the thread - thanks Joe and Thomas!)

Examples:
cisprime(2-4*i) returns 0
cisprime(-2+5*i) returns 1

Source: http://mathworld.wolfram.com/GaussianPrime.html
11-12-2014, 04:41 PM
Post: #2
 Jim Horn Member Posts: 171 Joined: Dec 2013
RE: Complex Prime Number Test
Wow - never heard of those before. Thanks for teaching us!

I am puzzled - your program tests for 3mod4 of the non-zero component if the other is zero, but doesn't test the non-zero component for primality. So, for example, 0+/- 15i isn't a Gaussian prime as 15 isn't prime. Am I mistaken?
11-12-2014, 05:31 PM
Post: #3
 Thomas Klemm Senior Member Posts: 1,448 Joined: Dec 2013
RE: Complex Prime Number Test
(11-12-2014 04:41 PM)Jim Horn Wrote:  I am puzzled - your program tests for 3mod4 of the non-zero component if the other is zero, but doesn't test the non-zero component for primality. So, for example, 0+/- 15i isn't a Gaussian prime as 15 isn't prime. Am I mistaken?

Quote:If a=0, then bi is a Gaussian prime iff |b| is an ordinary prime and |b|=3 (mod 4).

Thus 15i is not a Gaussian prime since 15 is not an ordinary prime.
However 5 is not a Gaussian prime though it is an ordinary prime since |5|=1 (mod 4).
The complex factors of 5 are (2 + i)(2 − i).

HTH
Thomas
11-13-2014, 01:23 PM
Post: #4
 Eddie W. Shore Senior Member Posts: 975 Joined: Dec 2013
RE: Complex Prime Number Test
(11-12-2014 05:31 PM)Thomas Klemm Wrote:
(11-12-2014 04:41 PM)Jim Horn Wrote:  I am puzzled - your program tests for 3mod4 of the non-zero component if the other is zero, but doesn't test the non-zero component for primality. So, for example, 0+/- 15i isn't a Gaussian prime as 15 isn't prime. Am I mistaken?

Quote:If a=0, then bi is a Gaussian prime iff |b| is an ordinary prime and |b|=3 (mod 4).

Thus 15i is not a Gaussian prime since 15 is not an ordinary prime.
However 5 is not a Gaussian prime though it is an ordinary prime since |5|=1 (mod 4).
The complex factors of 5 are (2 + i)(2 − i).

HTH
Thomas

Thomas,

Thanks for pointing out the glaring omission - much appreciated. The edited algorithm should be correct now.

Eddie
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)