Gaussian Integers

Definition

Gaussian integers are complex numbers of the form

$a+bi,$

where $a$ and $b$ are integers.

Like other complex numbers, Gaussian integers can be added, subtracted, and multiplied . For example: $\begin{aligned} \text{ Addition:} & (2-3i)+(4+5i)=6+2i,\\ \text{ Subtraction:} & (2-3i)-(4+5i)=-2-8i,\\ \text{Multiplication:} & (2-3i)\cdot(4+5i) = 8+ 10i-12i-15i^2=23-2i. \end{aligned}$

Here are some examples and properties of Gaussian integers:

1. $2-3i, 4+5i, \ 17,\ 0$ are all Gaussian integers, while $\frac{4}{3}$, $\sqrt{2}$, and $-\frac{1}{2}+\frac{\sqrt{3}}{2}i$ are not.

2. The conjugate of $a+bi$ is $\overline{a+bi}=a-bi$, which is again a Gaussian integer.

3. The norm of $a+bi$ is $N(a+bi)=(a+bi)(a-bi)=a^2+b^2$, which is a non-negative integer.

4. The absolute value of a Gaussian integer is the (positive) square root of its norm: $\lvert a+bi \rvert =\sqrt{a^2+b^2}$.

5. There are no positive or negative Gaussian integers and one cannot say that one is less than another. One can, however, compare their norms.

One of the most useful concepts for Gaussian integers is the norm

$N(a+bi)=a^2+b^2.$

The norm is always a non-negative integer, and is multiplicative (i.e., the norm of the product is the product of the norms). We say that a Gaussian integer $z$ is a unit if $\frac{1}{z}$ is also a Gaussian integer. A Gaussian integer $(a+bi)$ is a multiple of Gaussian integer $(c+di)$ if

$(a+bi)=(c+di)\cdot (e+fi)$

for some Gaussian integer $e+fi$. In this case we say that $c+di$ divides $a+bi$, and use the notation

$(c+di) \mid (a+bi).$

A Gaussian integer is called prime if it is not equal to a product of two non-unit Gaussian integers. Otherwise, it is called composite. Clearly, multiplying by a unit does not change primality. Note that a number may be prime as a usual integer, but composite as a Gaussian integer (for example $5=(2+i)(2-i)$).

In the following sequence of theorems, we give a classification of Gaussian units and Gaussian primes.

Theorem 1. For a Gaussian integer $z=(a+bi),$ the following three statements are equivalent:

1. $z$ is a unit, i.e. $\frac{1}{z}$ is a Gaussian integer.

2. $N(z)=1$.

3. $z$ is $1,\ -1,\ i,$ or $-i$.

Proof. $1)\Rightarrow 2)$ Suppose $\frac{1}{x}=y$. Then $1=xy$, so $N(1)=N(x)N(y)$. Since $N(1)=1$ and $N(x)$ and $N(y)$ are integers, we have $N(x)=1$.

$2)\Rightarrow 3)$ We have

$N(z) = N(a+bi)=a^2+b^2 =1$

for integers $a$ and $b$. Then $a^2=1-b^2\leq 1$ and, similarly, $b^2\leq 1$, implying one of $a$ or $b$ must be $1$ and the other must be $0$.

$3)\Rightarrow 1)$ This can be checked directly: $\frac{1}{\pm1}=\pm1,\ \frac{1}{\pm i}=\mp i.$ $_\square$

Now that we know all the units, we want to classify all Gaussian primes. Here is a first result in this direction.

Theorem 2. Suppose $p=a+bi$ is a Gaussian prime and its norm $a^2+b^2$ is even. Then $a^2+b^2=2$ and $p$, up to a unit, is $1+i$.

Proof. Note that $2=(1+i)(1-i)$. The integers $a$ and $b$ are either both even or both odd. In the first case, $p$ is divisible by $2$, which is divisible by $(1+i)$. In the second case, $p+(1+i)$ is divisible by $2$. So in both cases $p$ is divisible by $1+i$. Because $p$ is prime, it must equal $e(1+i)$, where $e$ is a unit. $_\square$

The following theorems are classical results from elementary number theory that are important for the theory of Gaussian integers. We will skip their proofs.

Theorem 3. Suppose $p$ is an odd prime. Then the congruence $x^2+1 \equiv 0 \pmod p$ has a solution if and only if $p\equiv 1 \pmod 4$.

&nsbp;

Theorem 4. (Fermat's Two-Square Theorem) An odd prime $p$ can be expressed as $u^2+v^2$ for integers $u$ and $v$ if and only if $p\equiv 1\pmod 4.$

(Brahmagupta-Fibonacci Identity) Given two numbers, each of which can be written as the sum of two squares, their product can also be written as the sum of two squares. The identity is:

$(a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2.$

The above theorems suggest the following:

Theorem 5.

a) If $p=4k+1$ is a prime and $p=u^2+v^2$, then $u+vi$ and $u-vi$ are Gaussian primes.

b) If $p=4k+3$ is a prime in ${\mathbb N},$ then it is a prime in ${\mathbb Z}[i]$.

Proof. Recall that the norm of a product of two Gaussian integers equals the product of their norms.

a) The norm of $u\pm vi$ is $p$, so if $u\pm vi$ is equal to a product of two Gaussian integers, one of the factors must have norm $1$, which makes it a unit.

b) If $p=4k+3$ is a product of non-unit Gaussian integers, then, because its norm is $p^2$, the factors must have norm $p$. This is impossible by Theorem 4. $_\square$

Finally, we give a proof of the classification of Gaussian primes based on the uniqueness of prime factorization of Gaussian integers. Another, self-contained proof is given in the Worked Examples.

Theorem 6. (Classification of Gaussian Primes) All Gaussian primes are those described in Theorem 5.

Proof. Suppose $a+bi$ is a Gaussian prime. Consider

$a^2+b^2=(a+bi)(a-bi).$

We can decompose $a^2+b^2$ into a product of usual primes. Then for the prime $2$, write $2=(1+i)(1-i)$ and for the primes $p=4k+1$ write $p=(u+vi)(u-vi)$ . Because of the uniqueness of the decomposition into a product of primes, $a+bi$ must be one of the primes defined above, proving the theorem.

Worked Examples

1. Find all Gaussian primes with norm up to $20.$

Solution: By the classification, up to units, $1+i$ is the only Gaussian prime with norm $2$. If $p$ is prime of the form $p=4k+3$, the norm is $p^2$, so we must have $p=3$. For primes $p=4k+1,$ $p$ is $5,13,$ or $17$. Note that $5=2^2+1^2,$ $13=3^2+2^2$, and $17=4^2+1^2$. Therefore, the Gaussian primes with norm up to $20$ are, in increasing order of norm:

$1+i, 2+i, 2-i, 3, 3+2i, 3-2i, 4+i, 4-i.$

2. Suppose $a+bi$ is a Gaussian integer and suppose $p=4k+3$ divides $a^2+b^2$. Show $p|a+bi$.

Solution: If $b\neq 0 \pmod p,$ then consider $x\equiv \frac{a}{b} \pmod p$. We have $x^2+1=\frac{a^2+b^2}{b^2} \equiv 0 \pmod p$. From Theorem 3, this is impossible. So $p|b$, implying $p|a^2$ and $p|a$. Therefore, $p|a+bi.$

3. Suppose $a+bi$ is a Gaussian integer, and $p=4k+1$ divides $a^2+b^2$. Suppose $p=u^2+v^2.$ Show that either $u+vi|a+bi$ or $u-vi|a+bi$ (or both).

Solution: Note that $p=(u+vi)(u-vi)$. If $p|b$, then, as in the Example 2, $p|a+bi$, so both $u+vi$ and $u-vi$ divide $a+bi.$ If $b\neq 0 \pmod p,$ consider an integer $c$ such that $\frac{a}{b}\equiv c \pmod p$. Then $c^2+1\equiv 0 \pmod p$. Similarly, $\frac{u}{v}\equiv x \pmod p$ for some integer $x$. Because

$(x-c)(x+c)=x^2-c^2 \equiv 0\pmod p,$

either $c\equiv x \pmod p$ or $c\equiv -x \pmod p$. In the first case, for an integer $k\equiv \frac{b}{v} \pmod p,$ we have $b\equiv kv \pmod p$ and $a\equiv ku\pmod p$. So $(a+bi)-k(u+vi)$ is a multiple of $p$, so $a+bi$ is a multiple of $u+vi$. Similarly, in the second case $a+bi$ is a multiple of $u-vi.$

4. Show that all Gaussian primes are among those described in Theorem 2 and Theorem 5.

Solution: Suppose $a+bi$ is a Gaussian prime, and $N$ is its norm. Because it is not zero and not a unit, $N\geq 2$. From Theorem 2, Example 2 and Example 3, $a+bi$ is a multiple of one of the known Gaussian primes. Because $a+bi$ is a prime, the ratio must be a unit, which implies the result.

The Fundamental Theorem of Arithmetic states that every positive integer can be uniquely expressed as a product of positive primes, up to the order of multiplication. Can we create a system where it is not true?

Example. Consider the set $\mathbb{N}_{1}$ of all positive integers of the form $4k+1$, where $k$ is a positive integer. A product of any two such integers in $\mathbb{N}_1$ is again an integer of this form. We will call an integer from $\mathbb{N}_1$ prime if it is not a product of two smaller integers from $\mathbb{N}_{1}$, and the integer is called composite otherwise. By definition, every integer from $\mathbb{N}_{1}$ is a product of primes from $\mathbb{N}_1$. However, the product may not be uniquely expressed. For example, we can see that $9, 21, 49$ are all primes in $\mathbb{N}_1$, and we have $441 = 9 \cdot 49 = 21 \cdot 21$.

Of course, $\mathbb{N}_1$ is very different from integers or natural numbers, but this showcases the fact that there must be a reason for why the prime decomposition is unique. The deep reason is the existence of the division algorithm that produces a remainder that is strictly smaller than the divisor. Interestingly, the same property holds for the Gaussian integers, with respect to the norm:

Lemma 1. (Division algorithm) Suppose $x$ and $y$ are Gaussian integers, $y\neq 0$. Then there exist Gaussian integers $z$ and $r$ such that $x=yz+r$ and $|r|<|y|.$

Proof. Dividing $x$ by $y$, we get a number $a+bi$ where $a$ and $b$ are rational (not necessarily integers). Suppose $n$ is the closest integer to $a$ and $m$ is the closest integer to $b$. Denote $z=n+mi$. Then $|\frac{x}{y}-z|= |(a-n)+(m-b)i| \leq \sqrt{(\frac{1}{2})^2+ (\frac{1}{2})^2}=\frac{1}{\sqrt{2}}<1.$ So if $r=x-yz,$ then $|r|=|y|\cdot |\frac{x}{y}-z|<|y|.$ $_ \square$

This property is called the Euclidean domain property. In fact, in every Euclidean domain the factorization into a product of primes is unique. We present an argument for the Gaussian integers, which can be easily adapted for the regular integers. The following lemma is needed in the proof, and is known as Euclid's Lemma when restricted to integers.

Lemma 2. Suppose $p$ is a prime Gaussian integer and $p$ divides $uv,$ for some Gaussian integers $u$ and $v$. Then $p|u$ or $p|v$.

Proof. Consider the set $I$ of all Gaussian integers of the form $yu+zp$ for arbitrary Gaussian integers $y$ and $z$. This is also known as the ideal generated by $u$ and $p$. It has the property that any sum or difference of two elements from $I$ is in $I$, and any Gaussian integral multiple of an element from $I$ is in $I$. Suppose $a$ is the element of $I$ with the smallest possible non-zero absolute value. From Lemma 1, every element of $I$ is a multiple of $a$, otherwise the non-zero remainder, which also lies in $I$, will have a smaller absolute value. In particular, $a|p$. Because $p$ is prime, either $\frac{p}{a}$ is a unit or $a$ is a unit. In the first case, $u$ is a multiple of $a$, so it is a multiple of $p$. In the second case, multiplying $a$ by $\frac{1}{a}$, we express $1$ as $yu+zp$. Multiplying by $v$, we get $v=y(uv)+zvp$. Because $p|uv,$ this implies that $p|v$. $_ \square$

Theorem 1. (Unique Factorization Property) Every non-zero Gaussian integer can be uniquely expressed as a product of Gaussian primes, up to ordering and multiplication by units.

Proof. First we prove that a factorization into a product of primes always exists. If not, take $x$ to be the Gaussian integer with smallest absolute value which is not a product of primes. Then $x$ is not a prime, so $x=x_1x_2,$ a product of two non-zero, non-unit Gaussian integers. Since norms are multiplicative and positive integers, $x_1, x_2$ must have smaller norm than $x$, so they are both products of primes. If so, $x= x_1 x_2$ is also the product of primes, hence a contradiction.

Now we will prove the uniqueness. Suppose that $x$ is the Gaussian integer with smallest norm that admits two substantially different decompositions into a product of primes:

$x=p_1p_2 \ldots p_s=q_1q_2 \ldots q_t.$

Applying lemma 2 to $p=p_1$, $u=q_1$, $v=q_2...q_t$ we get that either $p_1|q_1$ or $p_1|q_2...q_t$. In the second case we apply it again, and again... as a result we get that $p_1$ must divide $q_k$ for some $k$. Because the number $q_k$ is prime, this means that $q_k$ is up to a unit $p_1$. Then we can cancel them out, and get a new $x,$ with two different prime decompositions and smaller norm. This contradicts our choice of $x$. $_ \square$

Another property of the Euclidean domain, very much related to the Unique Decomposition, is the existence of the Euclidean Algorithm for finding the greatest common divisor. This algorithm, as well as the uniqueness of prime decomposition for the usual integers goes all the way back to Euclid's Elements!

The Euclidean Algorithm works as follows: Suppose $x$ and $y$ are (Gaussian) integers. We order the pair $(x,y),$ so that $N(x)\geq N(y)$ and call it $(x_0,y_0)$. Then we use it to get new pairs, $(x_1,y_1),\ (x_2,y_2),...$ as follows. At every step, we divide $x_i$ by $y_i$. If the remainder is zero, we stop, and claim that $y_i$ the greatest common divisor of $x$ and $y$, denoted $\gcd(x,y)$. If there is a non-zero remainder, i.e. $x_i=y_iz_i+r_i,$ we take $(x_{i+1},y_{i+1})=(y_i,r_i)$ and continue.

Theorem 2.

1) For every initial pair $(x,y)$, the Euclidean algorithm terminates after a finite number of steps.

2) The number $\gcd(x,y)$ divides both $x$ and $y$, and every (Gaussian) integer $d$ that divides both $x$ and $y$ must divide $\gcd (x,y)$.

Proof. 1) For the Gaussian integers, note that $N(y_{i+1})=N(r_i)<N(y_{i})$, and the norm, being a positive integer, cannot decrease indefinitely.

Proof. 2) Suppose $\gcd(x,y)=y_i$. Then it clearly divides $x_i$ and $y_i$. Because $y_{i-1}=x_i$ and $x_{i-1}=y_{i-1}z_{i-1}+r_{i-1}=x_iz_{i-1}+y_i,$ it divides $x_{i-1}$ and $y_{i-1}$. Continuing in this manner, we prove that $\gcd(x,y)$ divides $x$ and $y$.

If $d$ divides both $x=x_0$ and $y_0$, then it divides $x_1=y_0$ and $y_1=x_0-y_0z_0$. Continuing in this manner, we prove that $d$ divides $y_i=\gcd(x,y)$. $_\square$

We finish this post by reproducing one of the recent proofs of the Fermat Two Squares Theorem, due to Don Zagier. An involution is such map $\phi$ from a set to itself, that $\phi(\phi(x))=x$ for all elements $x$.

Don Zagier's One-Sentence Proof of Fermat Two Squares Theorem. (Amer. Math. Monthly 97 (1990), no. 2, 144).

The involution on the finite set $S=\{(x,y,z)\in {\mathbb N}^3: x^2+4yz=p\}$ defined by

$(x,y,z) \rightarrow \begin{cases} (x+2z,z,y-x-z), & \text{if } x < y-z\\ (2y-x,y,x-y+z),& \text{if } y-z < x < 2y\\ (x-2y,x-y+z,y), & \text{if } x > 2y \\ \end{cases}$

has exactly one fixed point, so $|S|$ is odd and the involution defined by $(x, y, z) \to (x, z, y)$ also has a fixed point. $_\square$