Complex Prime Number Test

[Eddie W. Shore]

(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