In elementary number theory, Euclid's algorithm is often applied to calculate the greatest common divisor of two integers. In this article, we first prove the unique factorization theorem (UFT) for Z\mathbb Z using Euclid's algorithm. Then, we develop the Euclid's algorithm for Gaussian integers Z[i]\mathbb Z[i] and show that Gaussian integers can also be factorized uniquely.

Euclid's algorithm for Z\mathbb Z

Euclid's algorithm relies on the following fact for integers:

Division algorithm: Let a,bZa,b\in\mathbb Z then there exists qZq\in\mathbb Z such that 0abq<b0\le a-bq<b.

As a result, we can construct integer sequences q1,q2,,qnq_1,q_2,\dots,q_n and b>r1>r2>>rn1b>r_1>r_2>\dots >r_n\ge1 such that

a=q1b+r1,b=q2r1+r2,r1=q3r2+r3,r2=q4r3+r4,rn1=qn+1rn.\begin{aligned} a&=q_1b+r_1, \\ b&=q_2r_1+r_2, \\ r_1&=q_3r_2+r_3, \\ r_2&=q_4r_3+r_4, \\ &\vdots \\ r_{n-1}&=q_{n+1}r_n. \end{aligned}

Since the common divisors of aa and bb are also the comon divisors of aa and a±ba\pm b, we have

gcd(a,b)=gcd(r1,b)=gcd(r1,r2)=gcd(r2,r3)==gcd(rn1,rn),\gcd(a,b)=\gcd(r_1,b)=\gcd(r_1,r_2)=\gcd(r_2,r_3)=\dots=\gcd(r_{n-1},r_n),

so it follows from the definition of rn1r_{n-1} that rn=gcd(a,b)r_n=\gcd(a,b).

Having derived Euclid's algorithm for Z\mathbb Z, let's see how we can deduce from it the UFT of Z\mathbb Z.

Existence of prime factorization in Z\mathbb Z

Before proving every integer greater than one can be expressed as a product of primes uniquely, we first need to ensure that it is actually expressible by the product of primes.

Let n>1n>1 denote an integer and Dn\mathcal D_n denote the set of its divisors greater than one. Because n=1nn=1\cdot n, we know that Dn\mathcal D_n must be nonempty. Combining this with the fact that DnZ>0\mathcal D_n\subset\mathbb Z_{>0}, we conclude from well-ordering principle that Dn\mathcal D_n has a minimal element greater than one. It is certain that this minimal element is a prime, or otherwise the transitivity of divisibility allows us to find an even smaller element in Dn\mathcal D_n. Thus, we see that every integer greater than one has a prime divisor.

Now, let N\mathcal N denote the set of integers greater than one that are not the product of primes. If N\mathcal N is not empty, then well-ordering principle guarantees the existence of the minimal element mNm\in\mathcal N. Since m>1m>1, we see that there exists a prime p2p\ge2 that divides mm, so it follows from m/p<mm/p<m that m/pm/p is a product of primes, reaching contradiction. Consequently, every integer greater than one is a product of primes.

Having proven the existence of factorization, we now proceed to prove its uniqueness.

Euclid's lemma and UFT in Z\mathbb Z

In this section, we show that UFT can be deduced from the following fact:

Euclid's lemma: If gcd(a,b)=1\gcd(a,b)=1 and bacb\vert ac then bcb\vert c.

When bb is a prime number, Euclid's lemma becomes the following:

For prime pp, if pabp\vert ab and gcd(a,b)=1\gcd(a,b)=1 then one of pap\vert a and pcp\vert c must be true.

From this statement, we prove UFT:

Proof of UFT. Let's suppose we can write n>1n>1 in the following two ways

n=p1a1p2a2prar=q1b1q2b2qsbs.n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}=q_1^{b_1}q_2^{b_2}\dots q_s^{b_s}.

where p1<p2<<prp_1<p_2<\dots<p_r and q1<q2<<qsq_1<q_2<\dots<q_s denote primes and ai,biZ>0a_i,b_i\in\mathbb Z_{>0}. By Euclid's lemma, we see that for any 1ir1\le i\le r there exists a unique 1js1\le j\le s such that pi=qjp_i=q_j, so we must have r=sr=s. In addition, we must have ai=bja_i=b_j or otherwise n/pimin(ai,bj)n/p_i^{\min(a_i,b_j)} would be divisible by pip_i, reaching a contradiction. \square

Proof of Euclid's lemma. By definition we know that b(ac,bc)b\vert(ac,bc). Multiplying both side of the Euclid algorithm by cc we have

ac=q1bc+r1c,bc=q2r1c+r2c,r1c=q3r2c+r3c,r2c=q4r3+r4c,rn1c=qnrnc,\begin{aligned} ac&=q_1bc+r_1c, \\ bc&=q_2r_1c+r_2c, \\ r_1c&=q_3r_2c+r_3c, \\ r_2c&=q_4r_3+r_4c, \\ &\vdots \\ r_{n-1}c&=q_nr_nc, \end{aligned}

This indicates that (ac,bc)=rnc=gcd(a,b)c=c(ac,bc)=r_nc=\gcd(a,b)c=c. \square

Up to now, we have merely justified unique factorization for integer greater than one. However, by symmetry we can generalize it to negative integers. For convenience, let ±1\pm1 be called units of Z\mathbb Z and nZn\in\mathbb Z and let n,nZn,-n\in\mathbb Z be called associates of each other. Then, we can extend the definition of primes to Z\mathbb Z:

Prime numbers in Z\mathbb Z: An integer pp is a prime if and only if its only divisible by units and its associates.

With these considered, we can state the UFT for Z\mathbb Z in the following way:

UFT for Z\mathbb Z: Every number in Z\mathbb Z, not zero or a unit, can be expressed as a product of primes, and the representation is unique apart from the order of primes, presence of units in factorizations, and ambiguity of associate primes.

Under this definition, (2)×3(-2)\times3, (1)×(2)×(3)(-1)\times(-2)\times(-3), and 2×(3)2\times(-3) are considered the same factorization of 6-6.

Remarks on Euclid's algorithm

From the previous sections, we derive the UFT for Z\mathbb Z in the following order:

  1. Division algorithm
  2. Euclid's algorithm
  3. Euclid's lemma
  4. Unique factorization theorem

In the rest of this article, we see that we can replicate this process in the justification of UFT for Z[i]\mathbb Z[i], and the key to this replication is Euclid's algorithm.

For convenience, we derive another consequence of Euclid's algorithm useful for latter investigation:

Bezout's lemma: Let a,ba,b be two integers, then ax+by=dax+by=d has integer solutions if and only if dd is a divisible by gcd(a,b)\gcd(a,b).

Proof. By definition, we see that whenever x,yZx,y\in\mathbb Z the number ax+byax+by must be an integer multiple of gcd(a,b)\gcd(a,b). Therefore, it suffices to show that ax+by=gcd(a,b)ax+by=\gcd(a,b) always has integer solutions.

Let q1,q2,,qnq_1,q_2,\dots,q_n and r1,r2,,rnr_1,r_2,\dots,r_n be defined as in Euclid's algorithm. Then we see that we can express rnr_n in terms of aa and bb using iterations:

Suppose rn=Pkrnk1+Qkrnkr_n=P_kr_{n-k-1}+Q_kr_{n-k}, then it follows from the definition of rnr_n that P0=1P_0=1 and Q0=qn1Q_0=q_n-1. For kn3k\le n-3, it follows from rnk=rnk2qnkrnk1r_{n-k}=r_{n-k-2}-q_{n-k}r_{n-k-1} that PkP_k and QkQ_k obeys the recursive relation:

{Pk+1=Qk,Qk+1=PkQkqnk.\begin{cases} P_{k+1} &=Q_k, \\ Q_{k+1} &=P_k-Q_kq_{n-k}. \end{cases}

This indicates that Pm,QmZP_m,Q_m\in\mathbb Z for all mn2m\le n-2. When m=n2m=n-2 we have

rn=Pn2r1+Qn2r2=(Pn2Qn2q2)r1+Qn2b=(Pn2Qn2q2)a+[Qn2+q1(Pn2Qn2q2)]b\begin{aligned} r_n &=P_{n-2}r_1+Q_{n-2}r_2=(P_{n-2}-Q_{n-2}q_2)r_1+Q_{n-2}b \\ &=(P_{n-2}-Q_{n-2}q_2)a+[Q_{n-2}+q_1(P_{n-2}-Q_{n-2}q_2)]b \end{aligned}

Setting x=Pn2Qn2q2x=P_{n-2}-Q_{n-2}q_2 and y=Qn2(1q1q2)+q1Pn2y=Q_{n-2}(1-q_1q_2)+q_1P_{n-2} completes the proof. \square

Basics of Z[i]\mathbb Z[i]

From the definition Z[i]={a+bi:a,bZ}\mathbb Z[i]=\{a+bi:a,b\in\mathbb Z\}, it is easily verified that the properties of divisibility Z\mathbb Z can be easily generalized to Z[i]\mathbb Z[i]. Moreover, because the deduction process of UFT from Euclid's lemma in the Z\mathbb Z situation does not make use of properties that are specific to Z\mathbb Z, we only need to prove Euclid's lemma for Z[i]\mathbb Z[i], which relies on the corresponding Euclid's algorithm.

Norms, units, and primes in Z[i]\mathbb Z[i]

To convenience our investigation, we let Nα=α2N\alpha=\lvert\alpha\rvert^2 be the norm of αZ[i]\alpha\in\mathbb Z[i]. If α=a+bi\alpha=a+bi for some a,bZa,b\in\mathbb Z then we have

Nα=αα=N(a+bi)=a2+b2N\alpha=\overline\alpha\cdot\alpha=N(a+bi)=a^2+b^2

Moreover, because

N(a+bi)N(c+di)=abbacddc=acbdad+bc(ad+bc)acbd=N[(a+bi)(c+di)],\begin{aligned} N(a+bi)N(c+di) &= \begin{vmatrix} a & b \\ -b & a \end{vmatrix}\cdot \begin{vmatrix} c & d \\ -d & c \end{vmatrix} \\ &= \begin{vmatrix} ac-bd & ad+bc \\ -(ad+bc) & ac-bd \end{vmatrix} \\ &=N[(a+bi)(c+di)], \end{aligned}

we see that if α,βZ[i]\alpha,\beta\in\mathbb Z[i] and αβ\alpha\vert\beta, then NαNβN\alpha\vert N\beta.

We can also define units and associates for Z[i]\mathbb Z[i] using norms:

Units in Z[i]\mathbb Z[i]: α\alpha is a unit of Z[i]\mathbb Z[i] if and only if Nα=1N\alpha=1.

Associates in Z[i]\mathbb Z[i]: α\alpha and β\beta are associates in Z[i]\mathbb Z[i] if and only if there exists a unit ϵ\epsilon such that α=ϵβ\alpha=\epsilon\beta.

Hence, the only units of Z[i]\mathbb Z[i] are ±1,±i\pm1,\pm i. With units well defined, we can introduce prime numbers in Z[i]\mathbb Z[i]:

Gaussian primes: A number in Z[i]\mathbb Z[i] is said to be prime if and only if it is not a unit and is only divisible by units and the associates of itself.

Division algorithm

In the situation of Z\mathbb Z, we can directly compare the size of integers, but in Z[i]\mathbb Z[i] we can only compare size of the norms. Thus, we should phrase the division algorithm in the following way:

Division algorithm for Z[i]\mathbb Z[i]: For any α,βZ[i]\alpha,\beta\in\mathbb Z[i] there exists γZ[i]\gamma\in\mathbb Z[i] such that N(αγβ)<NβN(\alpha-\gamma\beta)<N\beta.

Proof. Using the properties of complex conjugates, we have γ0=α/β=αβ/Nβ\gamma_0=\alpha/\beta=\alpha\overline\beta/N\beta.

If the real parts and imaginary parts of αβ\alpha\overline\beta are divisible by NβN\beta then γ0Z[i]\gamma_0\in\mathbb Z[i], and choosing γ=γ0\gamma=\gamma_0 completes the proof.

If otherwise, then γ0\gamma_0 must lie in a unit square formed by γ1,γ2,γ3,γ4Z[i]\gamma_1,\gamma_2,\gamma_3,\gamma_4\in\mathbb Z[i]. Because the distance of any points inside a square to the closest square vertex is always no more than half the diagonal, we conclude that there exist a γ{γ1,γ2,γ3,γ4}\gamma\in\{\gamma_1,\gamma_2,\gamma_3,\gamma_4\} such that γ0γ1/2\lvert\gamma_0-\gamma\rvert\le1/\sqrt2. This indicates that

N(αβγ)12N(β),N(\alpha-\beta\gamma)\le\frac12N(\beta),

which is a inequality stronger than the original statement. \square

Similarly, the greatest common divisor of Gaussian integers also needs to be redefined using norms:

Greatest common divisor in Z[i]\mathbb Z[i]: Let α,βZ[i]\alpha,\beta\in\mathbb Z[i]. If γ\gamma is said to be a greatest common divisor of α\alpha and β\beta if it is the common divisor of α\alpha and β\beta with the greatest norm.

The existence of such divisor can be justified by the well-ordering principle. From this definition, we observe easily that the greatest common divisor is unique apart from the ambiguities of associates. Moreover, α\alpha and β\beta are said to be coprime in Z[i]\mathbb Z[i] if and only if their only common divisors are units.

Finally, we are ready to deduce Euclid's algorithm for Z[i]\mathbb Z[i].

Euclid's algorithm for Z[i]\mathbb Z[i]

From division algorith, we see that for α,βZ[i]\alpha,\beta\in\mathbb Z[i] we can construct Z[i]\mathbb Z[i] sequences τ1,τ2,,τn\tau_1,\tau_2,\dots,\tau_n and γ1,γ2,,γn\gamma_1,\gamma_2,\dots,\gamma_n satisfying

Nβ>Nγ1>Nγ2>>Nγn1N\beta>N\gamma_1>N\gamma_2>\dots>N\gamma_n\ge1

and

α=τ1β+γ1,β=τ2γ1+γ2,γ1=τ3γ2+γ3,γ2=τ4γ3+γ4,γn1=τnγn.\begin{aligned} \alpha&=\tau_1\beta+\gamma_1, \\ \beta&=\tau_2\gamma_1+\gamma_2, \\ \gamma_1&=\tau_3\gamma_2+\gamma_3, \\ \gamma_2&=\tau_4\gamma_3+\gamma_4, \\ &\vdots \\ \gamma_{n-1}&=\tau_n\gamma_n. \end{aligned}

Since the common divisors of α\alpha and β\beta are also the common divisors of α±β\alpha\pm\beta, we conclude from the definition of γn1\gamma_{n-1} that γn\gamma_n is a greatest common divisor of α\alpha and β\beta.

With Euclid's algorithm ready, we can finally proceed to prove the UFT for Z[i]\mathbb Z[i].

Euclid's lemma and UFT for Z[i]\mathbb Z[i]

For an arbitrary αZ[i]\alpha\in\mathbb Z[i], let Dα\mathcal D_\alpha denote the set of divisors of α\alpha apart from units. Because αDα\alpha\in\mathcal D_\alpha, well-ordering principle guarantees the existence of γDα\gamma\in\mathcal D_\alpha having the smallest Nγ>1N\gamma>1. Using a proof-by-contradiction similar to the situation in Z\mathbb Z, we see that every member of Z[i]\mathbb Z[i] apart from zero and units is divisible by a prime in Z[i]\mathbb Z[i]. Applying a similar well-ordering-principle argument as before, we also see that every member of Z[i]\mathbb Z[i], not zero or a unit, is a product of Gaussian primes and units.

To show that the prime factorization is unique, we now proceed to prove the variant of Euclid's lemma for Z[i]\mathbb Z[i]:

Euclid's lemma for Z[i]\mathbb Z[i]: If α,βZ[i]\alpha,\beta\in\mathbb Z[i] are coprime and αβγ\alpha\vert\beta\gamma, then αγ\alpha\vert\gamma.

Proof. By definition, we know that α\alpha divides every greatest common divisor of αγ\alpha\gamma and βγ\beta\gamma. Multiplying both side of Euclid's algorithm by γ\gamma we see that γ\gamma is one of such greatest common divisor, thereby completing the proof.

Using the arguments similar to those for Z\mathbb Z, we obtain the UFT:

UFT for Z[i]\mathbb Z[i]: Every number in Z[i]\mathbb Z[i], not zero or a unit, can be expressed as a product of primes, and the representation is unique apart from the order of primes, presence of units in factorizations, and ambiguity of associate primes.

Application to the classification of Gaussian primes

Because the norm function N()N(\cdot) is strictly multiplicative, we see that every Gaussian integer whose norm is a prime is also a prime. The converse is not true as the norm of any primes of Z\mathbb Z is a square.

Viewing Z[i]\mathbb Z[i] from the complex plane, one easily finds it confusing to determine whether the Gaussian integers are prime or not. Luckily, there is a subtle result connecting primes in Z[i]\mathbb Z[i] and primes in Z\mathbb Z:

A Gaussian prime is a divisor of exactly one positive prime.

Proof. Denote the Gaussian prime by π\pi and Mπ\mathcal M_\pi the set of integers divisible by π\pi. Then by definition we have 1∉Mπ1\not\in\mathcal M_\pi and NπMπN\pi\in\mathcal M_\pi, and the well-ordering principle ensures that π\pi must divide at least one prime.

If π\pi divides two different positive primes p,pp,p'. Then it follows from Bezout's lemma that there exists x,yZx,y\in\mathbb Z such that px+qy=1px+qy=1. This indicates that π\pi must be a unit, which is a contradiction. \square

As a result of the theorem, we observe that every Gaussian primes can be identified by factorizing positive primes in Z[i]\mathbb Z[i]:

  • p=2p=2: Since 2=(1+i)(1i)2=(1+i)(1-i), we obtain 1+i1+i, 1+i-1+i, 1i1-i, and 1i-1-i.
  • p>2p>2 and not expressible as sum of two squares: we see that pp itself is a Gaussian prime.
  • p>2p>2 and expressible as sum of two squares. By UFT we can find unique a,bZ>0a,b\in\mathbb Z_{>0} such that p=a2+b2p=a^2+b^2, which gives ±a±bi\pm a\pm bi and ±b±ai\pm b\pm ai.

Conclusion

In this article, we begin from the elementary ground of Z\mathbb Z and explores the theoretical significance of Euclid's algorithm in the deduction of UFT in Z\mathbb Z. Finally, using the language of norms, we translate these arguments to give a proof of UFT in Z[i]\mathbb Z[i], and apply it to classify all types of Gaussian primes.

The topic of the current article is purely algebraic, but we will see in future articles that these algebraic properties, combined with analytic methods, would produce remarkable results in number theory.