|Re: Gaussian Primes|
Message #2 Posted by Egan Ford on 11 Mar 2010, 6:26 p.m.,
in response to message #1 by Gerry Schultz
Is it possible to write a program to calculate and display prime complex numbers? Could it use the same algorithms as is used to display integer primes?
A Gaussian integer a + bi is prime if and only if:
- one of a, b is zero and the other is a prime of the form 4n + 3 or its negative -(4n + 3) (where n >= 0)
- or both are nonzero and a2 + b2 is prime.
So, you should be able to modify your prime search program to test for (p-3)/4 is integer (got mod?, then p mod 4 = 3), if not, then since all primes not in the form 4n+3 are the sum of two squares, find the squares. Every odd prime number you find will fit the first or second case. So, all you are really doing is altering the output of any prime search program. In the first case you could report (0,p), (p,0), (-p,0), (0,-p) and in the second (a,b), (-a,b), (a,-b), (-a,-b).
Reporting all 4 for each case may be redundant. I'd just report to paper tape p or p:a,b, e.g.:
5 :1,2 4n+1 (sum of squares)
P.S. If you like the Riemann Hypothesis mixed with a bit of history then read Prime Obsession.
Edited: 11 Mar 2010, 7:27 p.m.