Euclid's Algorithm and Unique Factorization of Gaussian Integers
number-theoryIn 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 using Euclid's algorithm. Then, we develop the Euclid's algorithm for Gaussian integers and show that Gaussian integers can also be factorized uniquely.
Euclid's algorithm for
Euclid's algorithm relies on the following fact for integers:
Division algorithm: Let then there exists such that .
As a result, we can construct integer sequences and such that
Since the common divisors of and are also the comon divisors of and , we have
so it follows from the definition of that .
Having derived Euclid's algorithm for , let's see how we can deduce from it the UFT of .
Existence of prime factorization in
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 denote an integer and denote the set of its divisors greater than one. Because , we know that must be nonempty. Combining this with the fact that , we conclude from well-ordering principle that 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 . Thus, we see that every integer greater than one has a prime divisor.
Now, let denote the set of integers greater than one that are not the product of primes. If is not empty, then well-ordering principle guarantees the existence of the minimal element . Since , we see that there exists a prime that divides , so it follows from that 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
In this section, we show that UFT can be deduced from the following fact:
Euclid's lemma: If and then .
When is a prime number, Euclid's lemma becomes the following:
For prime , if and then one of and must be true.
From this statement, we prove UFT:
Proof of UFT. Let's suppose we can write in the following two ways
where and denote primes and . By Euclid's lemma, we see that for any there exists a unique such that , so we must have . In addition, we must have or otherwise would be divisible by , reaching a contradiction.
Proof of Euclid's lemma. By definition we know that . Multiplying both side of the Euclid algorithm by we have
This indicates that .
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 be called units of and and let be called associates of each other. Then, we can extend the definition of primes to :
Prime numbers in : An integer is a prime if and only if its only divisible by units and its associates.
With these considered, we can state the UFT for in the following way:
UFT for : Every number in , 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, , , and are considered the same factorization of .
Remarks on Euclid's algorithm
From the previous sections, we derive the UFT for in the following order:
- Division algorithm
- Euclid's algorithm
- Euclid's lemma
- Unique factorization theorem
In the rest of this article, we see that we can replicate this process in the justification of UFT for , 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 be two integers, then has integer solutions if and only if is a divisible by .
Proof. By definition, we see that whenever the number must be an integer multiple of . Therefore, it suffices to show that always has integer solutions.
Let and be defined as in Euclid's algorithm. Then we see that we can express in terms of and using iterations:
Suppose , then it follows from the definition of that and . For , it follows from that and obeys the recursive relation:
This indicates that for all . When we have
Setting and completes the proof.
Basics of
From the definition , it is easily verified that the properties of divisibility can be easily generalized to . Moreover, because the deduction process of UFT from Euclid's lemma in the situation does not make use of properties that are specific to , we only need to prove Euclid's lemma for , which relies on the corresponding Euclid's algorithm.
Norms, units, and primes in
To convenience our investigation, we let be the norm of . If for some then we have
Moreover, because
we see that if and , then .
We can also define units and associates for using norms:
Units in : is a unit of if and only if .
Associates in : and are associates in if and only if there exists a unit such that .
Hence, the only units of are . With units well defined, we can introduce prime numbers in :
Gaussian primes: A number in 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 , we can directly compare the size of integers, but in we can only compare size of the norms. Thus, we should phrase the division algorithm in the following way:
Division algorithm for : For any there exists such that .
Proof. Using the properties of complex conjugates, we have .
If the real parts and imaginary parts of are divisible by then , and choosing completes the proof.
If otherwise, then must lie in a unit square formed by . 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 such that . This indicates that
which is a inequality stronger than the original statement.
Similarly, the greatest common divisor of Gaussian integers also needs to be redefined using norms:
Greatest common divisor in : Let . If is said to be a greatest common divisor of and if it is the common divisor of and 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, and are said to be coprime in if and only if their only common divisors are units.
Finally, we are ready to deduce Euclid's algorithm for .
Euclid's algorithm for
From division algorith, we see that for we can construct sequences and satisfying
and
Since the common divisors of and are also the common divisors of , we conclude from the definition of that is a greatest common divisor of and .
With Euclid's algorithm ready, we can finally proceed to prove the UFT for .
Euclid's lemma and UFT for
For an arbitrary , let denote the set of divisors of apart from units. Because , well-ordering principle guarantees the existence of having the smallest . Using a proof-by-contradiction similar to the situation in , we see that every member of apart from zero and units is divisible by a prime in . Applying a similar well-ordering-principle argument as before, we also see that every member of , 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 :
Euclid's lemma for : If are coprime and , then .
Proof. By definition, we know that divides every greatest common divisor of and . Multiplying both side of Euclid's algorithm by we see that is one of such greatest common divisor, thereby completing the proof.
Using the arguments similar to those for , we obtain the UFT:
UFT for : Every number in , 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 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 is a square.
Viewing 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 and primes in :
A Gaussian prime is a divisor of exactly one positive prime.
Proof. Denote the Gaussian prime by and the set of integers divisible by . Then by definition we have and , and the well-ordering principle ensures that must divide at least one prime.
If divides two different positive primes . Then it follows from Bezout's lemma that there exists such that . This indicates that must be a unit, which is a contradiction.
As a result of the theorem, we observe that every Gaussian primes can be identified by factorizing positive primes in :
- : Since , we obtain , , , and .
- and not expressible as sum of two squares: we see that itself is a Gaussian prime.
- and expressible as sum of two squares. By UFT we can find unique such that , which gives and .
Conclusion
In this article, we begin from the elementary ground of and explores the theoretical significance of Euclid's algorithm in the deduction of UFT in . Finally, using the language of norms, we translate these arguments to give a proof of UFT in , 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.