Find the primes in $\mathbb{Q}(\sqrt{-1})$ which have a norm less than 6.

How do you approach this problem? Also how do you prove that you have indeed found ALL primes in $\mathbb{Q}(\sqrt{-1})$ which have a norm less than 6?

2. Hello,
Originally Posted by Pn0yS0ld13r
Find the primes in $\mathbb{Q}(\sqrt{-1})$ which have a norm less than 6.

How do you approach this problem? Also how do you prove that you have indeed found ALL primes in $\mathbb{Q}(\sqrt{-1})$ which have a norm less than 6?
An element of the quadratic field $\mathbb{Q}(\sqrt{-1})$ is in the form $a+b \sqrt{-1}$, where a and b are integers.
(so it's complex numbers)
The elements of this field are called Gaussian integers.

Conditions for a Gaussian integer to be prime are listed here : Gaussian Prime -- from Wolfram MathWorld

(note that you're asked for the norm to be less than 6, that is to say $a^2+b^2 < 36$)

3. Originally Posted by Pn0yS0ld13r
Find the primes in $\mathbb{Q}(\sqrt{-1})$ which have a norm less than 6.
A positive prime in $\mathbb{Z}$ will be called a Hacker prime and a Gaussian prime shall refer to any prime in $\mathbb{Z}[i]$. Thus, for example $2$ is a Hacker prime but it is not a Gaussian prime because $2=-i(1+i)^2$. Remember the units in $\mathbb{Z}[i]$ are the numbers $1,-1,i,-i$, so these guys cannot be primes (by definition). Two numbers $a,b\in \mathbb{Z}[i]$ are associate iff $a=bu$ where $u$ is a unit, therefore the associates of $a+bi$ are $-a-bi$, $-b+ai$, $b-ai$. Now remember that a Gaussian integer is a Gaussian prime then all its associates shall be Gaussian primes too, this means we do not need to check all the pairs Moo listed since we can ignore the associated ones.

If $\pi$ is a Gaussian prime then $N(\pi) = \pi \bar \pi = p_1 ... p_r$ where $p_1,...,p_r$ are Hacker primes. This means $\pi | p$ for some Hacker prime $p$. And so (by definition) $p = \pi \alpha$ where $\alpha \in \mathbb{Z}[i]$. Thus, $p^2 = N(p) = N(\pi \alpha) = N(\pi) N(\alpha)$. Since $N(\pi)>1$ this forces $N(\pi) = p \text{ or }p^2$. In the latter case this forces $N(\alpha)=1$ i.e. $\alpha$ is a unit and so $\pi$ is associate to a Hacker prime. In the former case $\pi$ is not associate to a Hacker prime. This gives us a necessary condition. Given a Gaussian integer we takes its norm, then for it to be a Gaussian prime it is necessary for the norm to be a Hacker prime or a square of a Hacker prime. Is this also sufficient? The answer is no! Just consider the example with $2$ above. However, if the norm is a Hacker prime then it is also sufficient, and this is simple to prove. Say that $N(\pi) = p$ where $p$ is a Hacker prime. If $\pi$ was not prime then $\pi = \alpha\beta$ where $\alpha,\beta$ are non-units, therefore, $p = N(\pi) = N(\alpha)N(\beta)$ - but this is impossible because $p$ cannot be factored non-trivially (since it is a Hacker prime). Therefore the only thing we really ought to check are Gaussian integers which have norm a Hacker prime squared. But as said above those Gaussian primes must be associate to Hacker primes, and so the problem reduces to finding all Hacker primes which remain Gaussian primes. Here is the following result which I will not prove (unless you want it): let $p$ be an odd Hacker prime (if $p=2$ then look at example above) if $p\equiv 1 ~ (\bmod 4)$ then $p$ is not a Gaussian prime and if $p\equiv 3 ~ (\bmod 4)$ then $p$ is a Gaussian prime.

Now we can solve the problem.

The (up to associates) Hacker primes are: $2,3,5$. By above the ones that remain Gaussian primes are just $3$. Since its associates are too Gaussian primes this means: $3,-3,3i,-3i$ are all Gaussian primes. Now we need to find those $a+bi$ so that $a^2+b^2$ is a Hacker prime. Since $(-a)^2 = a^2,(-b)^2=b^2$ we can restrict the problem to $0. This gives the primes: $1+i,1+2i,1+4i,2+3i,2+5i$. To complete the list just interchange $b$ for $a$ in $a+bi$ and change the signs to get all possible combinations.

4. Thank you Moo and ThePerfectHacker.
Wonderful explainations!