5
$\begingroup$

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).

  • 0
    Also asked here: [whats-a-nice-method-to-factor-gaussian-integers@stackoverflow.com](http://stackoverflow.com/questions/2269810/whats-a-nice-method-to-factor-gaussian-integers)2012-05-30
  • 0
    Factoring just to determine primality seems expensive.2012-05-30
  • 0
    From http://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)."2012-05-30
  • 0
    So the question was **not** about $z$ being non-decomposable over $\Bbb{Z}[i]$, unlike $-11+29i=(2+3i)(5+7i)$?2012-05-30

1 Answers 1

5

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}$.

  • 0
    I recognize these are necessary conditions but are they also sufficient?2012-05-30
  • 0
    @NoName Yes these are necessary and sufficient.2012-05-30
  • 0
    and why are they sufficient?2012-05-30
  • 3
    @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.2012-05-30