7
$\begingroup$

Which rational primes less than 50 are also Gaussian primes?

My attempt: First we need to list all of the rational prime numbers that are less than $50$

$1,2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47$

A Gaussian prime is defined as a Gaussian integer that is not the product of Gaussian integers of similar norm.

The $Z[i]$ norm is $norm(a+bi)=\mid a+bi \mid^2 = a^2+b^2$ We have to look at the norms to determine which rational prime is a Gaussian prime.

For example $4+i$ is a Gaussian prime because our norm is $norm(4+i)=4^2+(i)^2=4^2+(-1)^2=16+1=17$. Since $17$ is also a prime in a set of all integers, $4+i$ is not the product of Gaussian integers of smaller norm because no such norms divide 17.

Also we need to separate the prime factors into two groups: any prime factors congruent to 3 mod 4 and any prime factors congruent to 1 mod 4

So all of the numbers congruent to 3 mod 4 which is also in $4k+3$ format are $3,7,11,19,23,31,39,43$ and $47$. These numbers can't be expressed as the sum of two squares.

All of the numbers congruent to 1 mod 4 which is also $4k+1$ are $1,5,13,17,29,37$, and $41,$ so these numbers can be expressed as the sum of squares and can be expressed as Gaussian Integers as well.

$1=1^2+0^2 = (1+0i)(1-0i)$

$5=2^2+1^2=(2+i)(2-i)$

$13 =2^2+3^2=(2+3i)(2-3i)$

$17=4^2+1^2=(4+i)(4-i)$

$29=5^2+2^2=(5+2i)(5-2i)$

$37=6^2+1^2=(6+i)(6-i)$

$41=5^2+4^2=(5+4i)(5-4i)$

Now my problem is...how do I really know that these numbers which are represented as a sum of squares and Gaussian Integers is really a Gaussian Prime. I know 17 counts as one, and for some reason 2 is not a Gaussian Prime because $norm(1+i)=1+(i^2)=1+((-1)^2)=1+1=2$ is smaller than $norm(2^2)=4$. So the norm has to be the same value in order to be considered as a Gaussian Prime?

$\endgroup$
  • $\begingroup$ The reason $2$ is not a Gaussian prime is because it can be factored into $(1+i)(1-i)$. Or in terms of the norm, $N(2)=4$ means the number 2 is divisible by two numbers whose norms are 2. If you check it you will see that $N(1+i)=N(1-i)=1^2+1^2=2$. $\endgroup$ – ReverseFlow Nov 23 '14 at 9:23
  • $\begingroup$ hmmm so because 2 is divisible by 4 it's not a Gaussian prime? wait a sec.. 2 is divisible by 2 numbers? would those 2 numbers be 1 and 2? or divisible by $N(1+i)$ and $N(1-i)$ $\endgroup$ – usukidoll Nov 23 '14 at 9:25
  • $\begingroup$ You are confusing several things simultaneously. I will write an answer give me a sec. $\endgroup$ – ReverseFlow Nov 23 '14 at 9:26
  • $\begingroup$ thanks. this isn't in my book and my prof was being a show off on this. $\endgroup$ – usukidoll Nov 23 '14 at 9:31
1
$\begingroup$

The most important part of your question is the definition of Gaussian Prime. Associated with this definition is a function $N:\mathbb{N}[i]\rightarrow \mathbb{N}$ which we called the norm on $\mathbb{N}[i]$. The key point of your confusion comes from not understanding this function. This function is multiplicative. Also, be aware of its domain and codomain.

A number $a+bi\in\mathbb{N[i]}$ is said to be a Gaussian prime provided it satisfies one of the following properties:

1) If $a\not=0$ and $b\not=0,$ $a+bi\;\;$ is a Gaussian Prime iff the Norm $N(a+bi)$ is a prime.

2) If $a=0$, then $|b| \equiv 3 \mod 4.$

3) If $b=0$, then $|a| \equiv 3 \mod 4.$

Remark 1: It is pointless to think about "smaller" or "bigger" Gaussian primes because there is no order on the Complex plane. That is, we know $1<2$ on the number line but what does $1<i$ or $1>i$ mean on the complex plane? Not much, as it turns out.

Remark 2 Learn to distinguish between a number and its norm. The number $17$ is a regular prime, but it is not a Gaussian prime. For two reasons:

1) By definition, $17=17+0i$ so we apply part 3) and we get $|17|=1 \mod 4$. Hence, not prime.

2) Using the norm, $N(17)=17^2$. This is key, the norm of the number $17$ is $17^2$. Meaning, 17 factors over $\mathbb{N}[i]$. This is so because $N$ is multiplicative. Hence, there are two Gaussian integers whose norm is 17. They need not be the same, they could be different and have the same norm.

To answer your comment: 2 is not divisible by 4. Rather, the Norm of 2 is 4, $N(2)=4$. Because the norm is multiplicative, there exists Gaussian integers whose norms are the primes of $4$. That is, $N(2)=2*2 \implies \exists z_1,z_2$ such that $N(2)=N(z_1)N(z_2)=2*2.$ So you could say $z_1=1+i$ and $z_2=1-i$. Note the norm of each one separately is $2$, and they-the numbers themselves not their norms- multiply together to get $2$.

This should clarify you a bit.

$\endgroup$
  • $\begingroup$ so by 1, a+bi is a Gaussian Prime if and only if the norm (a+bi) is a prime ? So do we need to find numbers that are congruent to 3 mod 4? But wait any number congruent to 3 mod 4 can't be expressed as the sum of two squares $\endgroup$ – usukidoll Nov 23 '14 at 10:17
  • $\begingroup$ Read carefully, IF both $a,b$ are nonzero then that is true. BUT, if one of them is $0$ a different criteria applies. To answer your question: if both are nonzero then yes, just look for norms that are prime and you are done. $\endgroup$ – ReverseFlow Nov 23 '14 at 10:20
  • $\begingroup$ ah I see ... both a and b can't be equal to 0 otherwise we have to use the second or third criteria. Say we have the number 19. 19 is congruent to 3 mod 4 because I can only multiply 4 x 4 = 16 and 16 divided by 19 gives me a remainder of 3. ... I can't express 19 as a sum of squares. Also the $norm(19)=19^2=361$ $\endgroup$ – usukidoll Nov 23 '14 at 10:21
  • $\begingroup$ $19=19+0i$ hence the criteria that applies is not $1)$ but 3). Hence, although the norm is not a prime 19 is a Gaussian prime because it meets criteria 3). $\endgroup$ – ReverseFlow Nov 23 '14 at 10:22
  • $\begingroup$ Yes, that is correct. $\endgroup$ – ReverseFlow Nov 23 '14 at 10:23
2
$\begingroup$

What might really help you understand here is the concept of conjugate pairs. The conjugate of $a - bi$ is $a + bi$. And $(a - bi)(a + bi) = a^2 + b^2$, which should look very familiar because it's the norm function.

Given $p$ a "rational prime" (for lack of a better term) with nonzero real part but no imaginary part, its norm is $p^2$. But if $p = a^2 + b^2$, then it is composite in $\mathbb{Z}[i]$ and its factorization is $(a - bi)(a + bi)$. It is a very well known result that the only odd rational primes that are the sum of two squares are primes of the form $4k + 1$. For example, $13 = 3^2 + 2^2 = (3 - 2i)(3 + 2i)$, so $3 + 2i$ is a Gaussian prime but $13$ is not.

Thus, minding the special case $(1 - i)(1 + i) = 2$, to find the rational primes between $1$ and $50$ that are also Gaussian primes, we just take the rational primes in that range, remove $2$ and remove the rational primes of the form $4k + 1$. So we take $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$$ and whittle it down to $$3, 7, 11, 19, 23, 31, 43, 47.$$

The reason we can be absolutely sure that these really are Gaussian primes is by verifying their divisors. For example, what are the divisors of $3$ in $\mathbb{Z}[i]$? We only need to look at Gaussian integers with a norm of $9$ or less to find: $1, i, -1, -i, 3, 3i, -3, -3i$. These are just units and $3$ multiplied by units. Gaussian primes have exactly $8$ divisors.

As for $39$, it can't be expressed as a sum of two squares, but it is a composite number. If it's composite in $\mathbb{Z}$, it sure as heck is also composite in $\mathbb{Z}[i]$. Its factorization is $39 = 3(3 - 2i)(3 + 2i)$.

$\endgroup$
1
$\begingroup$

I'm surprised no one's been a jerk to you about listing 1 and 39 with the rational primes. There ought to be some civility in pointing out basic facts like that. The inclusion of 39 must have been a simple slip of the finger.

But the point still needs to be made that 1 is not a prime number, it is a unit. In an imaginary quadratic ring like $\mathbb{Z}[i]$, if $u$ is a unit, then $N(nu) = N(u)$. The units in $\mathbb{Z}[i]$ are $1, -1, i, -i$. These are not primes. So our list of potential Gaussian primes with real part but without imaginary part is therefore:

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$

Your definition of "Gaussian prime" is at best confusing and at worst imprecise. Let me give you a couple of definitions that you can carry over to other quadratic integer rings:

  • In $\mathbb{Z}[\sqrt{d}]$, the norm function is $N(a + b\sqrt{d}) = a^2 - db^2$. (If $d = -1$, this works out to $a^2 + b^2$). Also, the norm function is completely multiplicative, meaning that $N(mn) = N(m)N(n)$.
  • A number $p = a + b\sqrt{d}$ is irreducible if for every possible way of expressing it as $p = \alpha \beta$ (with both $\alpha$ and $\beta$ being numbers in $\mathbb{Z}[\sqrt{d}]$ it turns out that either either $\alpha$ or $\beta$ is a unit (but not both).
  • If $\mathbb{Z}[\sqrt{d}]$ is a unique factorization domain (as $\mathbb{Z}[i]$ is), then all irreducibles in that domain are prime numbers.

So we're looking to see which of the numbers from our list of potential primes are indeed irreducible in the domain of Gaussian integers and are therefore Gaussian primes. The norm function in $\mathbb{Z}[i]$ is $N = a^2 + b^2$. This means that we're essentially looking for prime numbers that can't be expressed as a sum of two squares.

I'm no historian, I don't know if Fermat proved this himself, but it's attributed to Fermat the theorem that if $p = a^2 + b^2$, then either $p = 2$ or $p \equiv 1 \pmod 4$. So then all we have to do is strike 2 and primes of the form $4k + 1$ off our list of Gaussian primes:

$3, 7, 11, 19, 23, 31, 43, 47$

If you still have doubts this is correct, you can put this sequence into the OEIS as a search. You should get Sloane's A002145 as a result, which includes the comment Natural primes which are also Gaussian primes.

I'm not going to get on your case about the supposed futility of asking for primes $p < 50$; instead I'm going to assume that you meant to ask for primes $p$ such that $N(p) < 50$. If you put your compass center at 0 on the complex plane and your compass pencil at 50, then draw the circle, you're essentially asking for all the primes within that circle. Our list of primes is quite incomplete at this point.

But we can easily quadruple that list with simple multiplication by units. That is,

$-3, -7, -11, -19, -23, -31, -43, -47$

$3i, 7i, 11i, 19i, 23i, 31i, 43i, 47i$

$-3i, -7i, -11i, -19i, -23i, -31i, -43i, -47i$

are all Gaussian primes! But we're still missing primes that have both a real and an imaginary part.

I hope you haven't forgotten about those natural primes that are Gaussian composites. If a natural prime $p = 2$ or $p \equiv 1 \pmod 4$, it can be expressed as $p = (a - bi)(a + bi)$, so $p$ is not a Gaussian prime but both $a - bi$ and $a + bi$ are Gaussian primes (this is probably a theorem, lemma or corollary in your book so I won't give a proof). Therefore we're now looking for Gaussian integers with nonzero real part $a$ and nonzero imaginary part $bi$ so that $a^2 + b^2 = p$, a natural prime. Since there is only one even natural prime (2), in almost all cases $a$ has to be odd and $b$ even or vice-versa, and in only four cases can both $a$ and $b$ be odd.

Limiting ourselves to $0 < a < 50$ and $0 < b < 50$, we obtain this list:

$1 + i$, $2 + i$, $3 + 2i$, $4 + i$, $5 + 2i$, $5 + 4i$, $6 + i$

Now simple multiplication by units will give you the other three lists necessary to complete your full list of Gaussian primes with norm less than 50.

To review: if $p$ is a Gaussian prime and $\Re(p) = 0$ or $\Im(p) = 0$, then $N(p)$ is a perfect square. But if $\Re(p) \neq 0$ and $\Im(p) \neq 0$, then $N(p)$ is a natural prime.

I think I know what you meant by "rational prime" and there are some authors who use it to mean the same thing; I find the term problematic for $\mathbb{Z}[i]$ but that's a whole other can of worms.

$\endgroup$
  • $\begingroup$ The user @Genomeme helped me understand this last night in chat. As long as my result is 3 mod 4, then I do have a Gaussian Prime. However, if my result is 1 mod 4 and I can express it as a sum of two squares, then it's not a Gaussian Prime. I do have 3,7,11,19,23,31,39,43, and 47 as the answer. $\endgroup$ – usukidoll Nov 24 '14 at 1:34
  • 2
    $\begingroup$ Why do you still have 39 in your answer? $\endgroup$ – Robert Soupe Nov 24 '14 at 2:28
  • $\begingroup$ that was a typo because 39 isn't a prime number to begin with. A 3 can easily destroy 39... because 13 x 3 = 39 $\endgroup$ – usukidoll Nov 24 '14 at 2:32
  • 1
    $\begingroup$ keep in mind that the question was posted after one in the morning last night, so there are bound to be some slips here and there. $\endgroup$ – usukidoll Nov 24 '14 at 2:41
  • $\begingroup$ You do know you can edit these things, right? If you think Bob's being arrogant when he points out $1$ and $39$ are not primes, that's nothing compared to some of what I've seen on this site. $\endgroup$ – Lisa Nov 24 '14 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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