Gaussian primes are
numbers which do not have
factors even in the realm of
complex numbers, for example 19. 17 is a
real prime, but it is not Gaussian prime because
(4+i)(4-i) = 16 + 1 = 17
yerricde provides a neat proof that, if a real number has any complex factors, they are of the form (a+bi) and (a-bi), to give a²+b², Over to him:
The only way a product of two complex numbers can be real is if the numbers have equal and opposite phase angles. This occurs for a complex number and its conjugate times a constant; if the constant is not 1, the number is not prime.
They are known as Gaussian primes due to the work of Karl Friedrich Gauss on complex numbers in his doctoral thesis.
Another result with Gaussian primes, which occured to me and surely to others before, is that any Mersenne prime must also be Gaussian prime. This is especially noteworthy in the light of the GIMPS, as they are also discovering the largest known Gaussian primes. The proof is remarkably simple, and so is presented here:
First, let p = any real prime (Mersenne or otherwise). p is now either Gaussian prime, or it is the sum of two squares. Assume the latter:
p = a² + b²
Now if a and b are both even, then we could say that a=2m and b=2n for some m,n ε N.
p = (2m)² + (2n)²
= 4(m² + n²)
This contradicts the original designation of p as a prime. Let us instead try a and b as odd, ie a=2m+1 and b=2n+1.
p = (2m+1)² + (2n+1)²
= 4m² + 4m + 1 + 4n² + 4n + 1
= 2(2m² + 2m + 2n² + 2n + 1)
Again, this contradicts the original designation. Therefore, p is either Gaussian prime (cannot be written as the sum of two squares), or a and b have opposite parity. In fact we can easily generalise this result to show that a and b must be relatively prime (share no factors).
Now let us take the Mersenne prime q, which can be written 2p-1, by definition as a Mersenne number. By the previous result, either this is Gaussian prime or it is the sum of an odd and an even square. Let us assume the latter:
2p-1 = (2m)² + (2n+1)²
= 4m² + 4n² + 4n+1
2p = 4m² + 4n² + 4n + 2
= 2(2m² + 2n² + 2n + 1)
2p-1 = 2m² + 2n² + 2n + 1
= 2(m²+n²+n) + 1
Clearly this is a contradiction, as 2p must be even and the right-hand side is odd. Therefore, if q is Mersenne prime, it must be Gaussian prime. QED.
A consequence of this proof is that the conjecture that there is an infinite number of Mersenne primes is equivilant to there being an infinite number of Gaussian primes - although the reverse is not true. Mersenne primes are a proper subset of Gaussian primes.
When attempting to factorize generic primes into complex factors, the above parity proof is very useful, as it effectively halves the number of factors that need to be considered.
Gaussian primes should not be confused with Gaussian integers. The latter are complex numbers, while Gaussian primes are integers but have no complex factors. However, the factors themselves must be Gaussian integers, just as real composite numbers have only integral factors.