Time for another installment of the series on algebraic number theory. Check here for previous articles.
In this installment we're going to look at an important property that some rings (such as ℤ) have, although most rings do not. But it is a useful and important property for proving many number theoretic results, which is why one bothers to consider it. We'll illustrate that soon.
But first we need a little terminology. In any ring, a unit is a ring element that has a multiplicative inverse which is also in the ring. For instance, in ℤ 1 and -1 are units, and they are the only units. Other rings of algebraic integers can have many units, and the set of units of the ring form an abelian group under multiplication. Determining this group of units, in fact, is one of the interesting computational issues in algebraic number theory.
Another important concept is that of a prime element of a ring. A little bit of care is required to define "prime" in a general ring, but essentially a prime element is one that has no factors other than itself and units. As far as divisibility and factors are concerned, units are essentially irrelevant, since they are invertible.
One of the most important properties that the integers have as a ring is unique factorization. That is, for any n∈ℤ, there is a unique way (apart from order and unit factors) to write n as a product of primes.
This fact can be proven using the order properties of ℤ, i. e. for every pair of distinct positive integers a, b, exactly one of a<b, a=b, or a>b is true. To begin with, this implies that for any pair of positive a,b∈ℤ, we can write a=qb+r with 0≤q and 0≤r<b. Reason: you can subtract b from a only a nonnegative but finite number of times (q) before the result is negative. This is because every number in the sequence a, a-b, a-2b, ... is strictly less than its predecessor, and if a is finite, there are only a finite number of distinct positive integers less than a. r is simply the last quantity before you have a negative number, and so 0≤r<b. The numbers q and r are uniquely determined by this procedure, and in fact there is a simple algorithm to find them, as we'll see in a moment.
For any positive integers a,b∈ℤ, we can define the greatest common divisor of the pair as the largest (positive) integer which divides both, written gcd(a,b), or simply (a,b). It may be, of course, that (a,b)=1, in which case we say a and b are relatively prime. As a matter of notation, if one number m divides another n, so that n=mq for some q∈ℤ, we write m|n. If this is not the case, then we write m∤n. (a,b) can be defined by the conditions that (a,b)|a, (a,b)|b, and if both c|a and c|b, then c|(a,b).
The Greek mathematician Euclid, known best for his geometry, was interested in number theory also. In addition to proving that there are infinitely many primes, he also gave a simple algrorithm for computing the greatest common divisior of two integers without explicitly factoring them – since factoring can be a relatively difficult process for large numbers. The algorithm is called, of course, the Euclidean algorithm.
To apply it, assume (without loss of generality) that a>b and write a=q1b+r1. Here, q1>0 and 0≤r1<b. Provided r1≠0 we can repeat the procedure and write b=q2r1+r2. We can repeat this procedure as long as the remainder rk isn't 0. If rk is the last nonzero remainder, then one notes that (a,b)|rk, because in fact (a,b) divides all such remainders in the process. But we also have rk-1=qk+1rk, hence rk|rk-1 and from rk-2=qkrk-1+rk, we find rk|rk-2 too. If we proceed back all the way we find rk|b and rk|a, hence rk|(a,b). Therefore rk=(a,b). In other words, (a,b) is the last nonzero remainder in this process.
But even nicer things are true. Go back to a=q1b+r1, so that r1=a-q1b. Similarly, r2= b-q2r1= b-q2(a-q1b)= Ma+Nb for some integers M and N (not necessarily positive). Proceding inductively, we have that (a,b)=Ma+Nb for some M,N∈ℤ. What this says is that a certain Diophantine equation can be solved for unknowns M and N if a, b (and hence (a,b)) are given. Note that if (a,b)>1, the equation d=Ma+Nb could not be solved if 1≤d<(a,b), because a solution would imply (a,b)|d.
We need one more fact about prime numbers. Suppose p is prime, and p|mn for some m,n∈ℤ. So by definition, mn=pq for some q∈ℤ. We claim that p must divide either m or n (perhaps both). For suppose that we don't have p|m, hence (p,m) can't be p. But p is prime, and (p,m)|p, so we must have (p,m)=1. Hence it is possible to write 1=Mp+Nm. Therefore n=n(Mp+Nm)=Mnp+Nmn=Mnp+Npq= p(Mn+Nq). In other words, p|n. This property possessed by primes in ℤ is not shared by "primes" in other rings of algebraic integers, as we shall soon see.
We now have all the facts we need to prove unique factorization in ℤ. The proof is done by supposing factorization isn't unique, and showing this leads to a contradiction. So suppose factorization isn't unique, and for some n there are two different factorizations of n (apart from units ±1). There cannot be any prime which occurs in one factorization but not the other, by the result of the preceding paragraph. Hence the same prime factors occur, but for at least one prime p we have n=Apr=Bps with 0<r<s, and (A,p)=(B,p)=1. Dividing through by pr reduces to the case where a prime occurs in one factorization but not the other, which is impossible. The contradiction proves the desired result.
It may seem "obvious" that factorization is unique, because we are so familiar with the fact this is true in ℤ that it is taken for granted. It may therefore be rather surprising that in many (in fact most) rings of algebraic integers, factorization is not unique. Unique factorization is actually a very special and rare occurrence, and a great deal of algebraic number theory is concerned with either trying to compensate for this "problem", or else trying to describe, in some sense, just how badly factorization fails to be unique.
In the next installment we'll explain why unique factorization is a useful property and look at some examples.
Tags: algebraic number theory, unique factorization.
In this installment we're going to look at an important property that some rings (such as ℤ) have, although most rings do not. But it is a useful and important property for proving many number theoretic results, which is why one bothers to consider it. We'll illustrate that soon.
But first we need a little terminology. In any ring, a unit is a ring element that has a multiplicative inverse which is also in the ring. For instance, in ℤ 1 and -1 are units, and they are the only units. Other rings of algebraic integers can have many units, and the set of units of the ring form an abelian group under multiplication. Determining this group of units, in fact, is one of the interesting computational issues in algebraic number theory.
Another important concept is that of a prime element of a ring. A little bit of care is required to define "prime" in a general ring, but essentially a prime element is one that has no factors other than itself and units. As far as divisibility and factors are concerned, units are essentially irrelevant, since they are invertible.
One of the most important properties that the integers have as a ring is unique factorization. That is, for any n∈ℤ, there is a unique way (apart from order and unit factors) to write n as a product of primes.
This fact can be proven using the order properties of ℤ, i. e. for every pair of distinct positive integers a, b, exactly one of a<b, a=b, or a>b is true. To begin with, this implies that for any pair of positive a,b∈ℤ, we can write a=qb+r with 0≤q and 0≤r<b. Reason: you can subtract b from a only a nonnegative but finite number of times (q) before the result is negative. This is because every number in the sequence a, a-b, a-2b, ... is strictly less than its predecessor, and if a is finite, there are only a finite number of distinct positive integers less than a. r is simply the last quantity before you have a negative number, and so 0≤r<b. The numbers q and r are uniquely determined by this procedure, and in fact there is a simple algorithm to find them, as we'll see in a moment.
For any positive integers a,b∈ℤ, we can define the greatest common divisor of the pair as the largest (positive) integer which divides both, written gcd(a,b), or simply (a,b). It may be, of course, that (a,b)=1, in which case we say a and b are relatively prime. As a matter of notation, if one number m divides another n, so that n=mq for some q∈ℤ, we write m|n. If this is not the case, then we write m∤n. (a,b) can be defined by the conditions that (a,b)|a, (a,b)|b, and if both c|a and c|b, then c|(a,b).
The Greek mathematician Euclid, known best for his geometry, was interested in number theory also. In addition to proving that there are infinitely many primes, he also gave a simple algrorithm for computing the greatest common divisior of two integers without explicitly factoring them – since factoring can be a relatively difficult process for large numbers. The algorithm is called, of course, the Euclidean algorithm.
To apply it, assume (without loss of generality) that a>b and write a=q1b+r1. Here, q1>0 and 0≤r1<b. Provided r1≠0 we can repeat the procedure and write b=q2r1+r2. We can repeat this procedure as long as the remainder rk isn't 0. If rk is the last nonzero remainder, then one notes that (a,b)|rk, because in fact (a,b) divides all such remainders in the process. But we also have rk-1=qk+1rk, hence rk|rk-1 and from rk-2=qkrk-1+rk, we find rk|rk-2 too. If we proceed back all the way we find rk|b and rk|a, hence rk|(a,b). Therefore rk=(a,b). In other words, (a,b) is the last nonzero remainder in this process.
But even nicer things are true. Go back to a=q1b+r1, so that r1=a-q1b. Similarly, r2= b-q2r1= b-q2(a-q1b)= Ma+Nb for some integers M and N (not necessarily positive). Proceding inductively, we have that (a,b)=Ma+Nb for some M,N∈ℤ. What this says is that a certain Diophantine equation can be solved for unknowns M and N if a, b (and hence (a,b)) are given. Note that if (a,b)>1, the equation d=Ma+Nb could not be solved if 1≤d<(a,b), because a solution would imply (a,b)|d.
We need one more fact about prime numbers. Suppose p is prime, and p|mn for some m,n∈ℤ. So by definition, mn=pq for some q∈ℤ. We claim that p must divide either m or n (perhaps both). For suppose that we don't have p|m, hence (p,m) can't be p. But p is prime, and (p,m)|p, so we must have (p,m)=1. Hence it is possible to write 1=Mp+Nm. Therefore n=n(Mp+Nm)=Mnp+Nmn=Mnp+Npq= p(Mn+Nq). In other words, p|n. This property possessed by primes in ℤ is not shared by "primes" in other rings of algebraic integers, as we shall soon see.
We now have all the facts we need to prove unique factorization in ℤ. The proof is done by supposing factorization isn't unique, and showing this leads to a contradiction. So suppose factorization isn't unique, and for some n there are two different factorizations of n (apart from units ±1). There cannot be any prime which occurs in one factorization but not the other, by the result of the preceding paragraph. Hence the same prime factors occur, but for at least one prime p we have n=Apr=Bps with 0<r<s, and (A,p)=(B,p)=1. Dividing through by pr reduces to the case where a prime occurs in one factorization but not the other, which is impossible. The contradiction proves the desired result.
It may seem "obvious" that factorization is unique, because we are so familiar with the fact this is true in ℤ that it is taken for granted. It may therefore be rather surprising that in many (in fact most) rings of algebraic integers, factorization is not unique. Unique factorization is actually a very special and rare occurrence, and a great deal of algebraic number theory is concerned with either trying to compensate for this "problem", or else trying to describe, in some sense, just how badly factorization fails to be unique.
In the next installment we'll explain why unique factorization is a useful property and look at some examples.
Tags: algebraic number theory, unique factorization.