[Brilliant Blog] Gaussian Integers III

[This post is targeted at a Level 5 student. This is a continuation of the blog post [Gaussian integers II](http://blog.brilliant.org/2013/02/26/gaussian-integers-ii/).]

You are probably used to the fact that every positive integer can be uniquely expressed as a product of positive primes, up to the order of multiplication. This property is called the Fundamental Theorem of Arithmetic. While this seems like an obvious fact, 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.

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)\to \begin{cases} (x+2z,z,y-x-z), & \mbox{if } x < y-z\\ (2y-x,y,x-y+z), & \mbox{if } y-z < x < 2y\\ (x-2y,x-y+z,y), & \mbox{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$

Test Yourself

1. Find the greatest common divisor of $2+4i$ and $3-i$.

2. Suppose $x$ and $y$ are Gaussian integers and $\gcd (x,y) =d$. Show that there exists some Gaussian Integers $u$ and $v$ such that $d=ux+vy$. Hint: In the Euclidean algorithm, write $d$ as $0\cdot x_i+ 1\cdot y_i$ and then backtrack.

3. Repeat the above to show that the integers $\mathbb{N}$ has the unique factorization property. If we tried to reproduce the steps to show that $\mathbb{N}_1$ has the unique factorization property, where would our proof break down?

4. (*) Fill in the details of the Don Zagier's proof.

Hint: Don't just stare at it, grab a piece of paper and a pencil and try to see what happens when that complicated map is applied twice. If you wish, try $p=5$ and $p=13$ first.