Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Give a Gaussian integer $z\in{Z[i]}$, how can I determine if $z$ is prime? I imagine there exists an algorithm that maps primality in $Z[i]$ to primality in Z. And for the case when $z\in{Z}$ I think we can just check that $z$ is a prime in $Z$ and $z=3$ (mod 4).

share|improve this question
    
    
Factoring just to determine primality seems expensive. –  NoName May 30 '12 at 21:51
    
From en.wikipedia.org/wiki/Gaussian_integer : "A Gaussian integer a+bi is a Gaussian prime if and only if either: (i) one of a, b is zero and the other is a prime number of the form 4n+3 (with n a nonnegative integer) or its negative -(4n+3), or (ii) both are nonzero and a^2+b^2 is a prime number (which will not be of the form 4n+3)." –  Steven Stadnicki May 30 '12 at 21:55
    
So the question was not about $z$ being non-decomposable over $\Bbb{Z}[i]$, unlike $-11+29i=(2+3i)(5+7i)$? –  draks ... May 30 '12 at 22:02

1 Answer 1

up vote 4 down vote accepted

If $z \in \mathbb{Z}[i]$ is truly complex, then the norm i.e. $\text{real}(z)^2+\text{imag}(z)^2$ should be a prime in $\mathbb{N}$. If $z \in \mathbb{Z}[i]$ is real or purely imaginary, then the real or imaginary part (whichever is non-zero) itself should be a prime of the form $3 \bmod 4$ in $\mathbb{Z}$.

share|improve this answer
    
I recognize these are necessary conditions but are they also sufficient? –  NoName May 30 '12 at 21:53
    
@NoName Yes these are necessary and sufficient. –  user17762 May 30 '12 at 21:53
    
and why are they sufficient? –  draks ... May 30 '12 at 22:03
2  
@draks Briefly, because of the properties of the norm on the Gaussian integers - if we had $z=xy$ then $|z|^2 = |x|^2|y|^2$. If $|z|^2$ is a prime number, then you're done; either $|x|^2$ or $|y|^2$ must be $1$, and so one of $x$ and $y$ is a unit. Likewise, if $z=p$ is real and congruent to 3 mod 4, then because $|z|^2=p^2$, any factorization must take the form $z=x\bar{x}$ with $|x|^2=p$; but if $x=a+bi$, this says that $a^2+b^2 = p$, and primes of the form $4n+3$ aren't the sum of two squares. –  Steven Stadnicki May 30 '12 at 22:37
    
Thanks $ $ $ $ $ $ –  draks ... May 30 '12 at 22:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.