San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley Tornado Alley USA |
---|
The Properties of Integers and Their Extension to Integral Domains |
---|
The set of integers under addition and multiplication have a tidy structure. Some can be factored and for each there exists a unique (up to a permutation) factorization in terms of primes; i.e., those integers which cannot be factored. This is known as The Fundamental Theorem of the Arithmetic of Integers. The task of this material is to prove this fundamental theorem and then see how the structure of integers can be generalized but such that properties such as unique factorization are maintained. But first let us attend to the proof of the fundamental theorem.
The operations of additiion and multiplication for the integers have special properties; i.e.,
In addition to the above algebraic properties of integers it is also true that integers have an ordering, <, which has the properties of:
Many of the proofs of properties of integers make use of the method of induction. It is therefore appropriate to consider and prove a couple of theorems concerning induction.
Proof:
Let S be the set of integers for which P is true. S contains 1. Consider the set ~S, the set of integers for which P is not true.
There must exist the smallest element of ~S, say m. This smallest element cannot be 1. Therefore m is greater than 1. Since m is
the smallest element of ~S the integer (m-1) is in S and P(m-1) is true. By assumption this means that P(m) is true contrary to
the assumption. This contradiction means that ~S must be empty and thus P is true for all n.
Proof:
Let S be the set of integers for which P is true. S contains 1. Consider the set ~S, the set of integers for which P is not true.
There must exist the smallest element of ~S, say m. This smallest element cannot be 1. Therefore m is greater than 1. Since m is
the smallest element of ~S for any integer less than m is in S and P(k) for any k less than m is true. By assumption this means that
P(m) is true contrary to
the assumption. This contradiction means that ~S must be empty and thus P is true for all n.
Proof:
If S is nonempty it contains at least one element. If S consists entirely of the element 0 the lemma is satisfied. If S is not the
singleton set {0} it contains a nonzero element a.
Since S is closed under subtraction it contains a−a=0. Likewise it contains 0−a=−a. Thus S contains at least one positive element, a or −a. Therefore by the well ordering property of integers it contains a least positive element h.
Since S is closed under addition and subtraction it contains mh for any integer m. This follows from the first induction theorem since if S contains kh for some integer k is also contains kh+h=(k+1)h and kh−h=(k−1)h.
Suppose S contained a positive element b which is not a multiple of h. Since h is the least positive element b would have to larger than h. Then b=kh+r where k is an integer and r is a nonnegative integer less than h. Since r=b−kh and both b and kh belong to S and S is closed under subtraction r would have to belong to S. Since 0≤r<h and h is the least positive integer belonging to S r has to be zero which means that b=kh, and thus b is a multiple of h contrary to the hypothesis defining b.
Proof:
For any two For integers a and b let S be the set {ja+kb for j and k integers}, all linear combinations of a and b.
Consider the sum of any two elements
z_{1} and z_{2} of S
Thus (z_{1}+z_{2}) belongs to S. Likewise (z_{1}−z_{2})=(j_{1}−j_{2})a+(k_{1}−k_{2})b also belongs to S.
Thus S satisfies the conditions for lemma on integer sets closed under addition and subtraction and hence there exists an integer h such that all elements of S are multiples of h and likewise all multiples of h are elements of S. Note that a and b belong to S because a=1*a+0*b and b=0*a+1*b. Therefore a and b must be multiples of h and hence h is a common divisor of a and b.
The greatest common divisor (gcd) of two integers a and b is defined as a common divisor which is an integer multiple of all other common divisors of a and b. Under this definition the gcd of a and b is not unique because if g is the gcd of a and b then so is −g. However the absolute value of the gcd's of a and b is unique. Hereafter gcd will refer to the positive value greatest common divisor.
Proof:
By the previous lemma there exists a least positive element h of the set of linear combinations of a and b; i.e.,
By definition g is a multiple of h, say g=mh. Thus
Thus there exist integers r and s such that g=ra+sb.
Proof:
Suppose p does not divide a. Then the greatest common divisor of a and p is 1. By the previous lemma there exist integers r and s
such that
This equation may be multiplied by b to give
Since p divides ab in the first term on the RHS of this equation and also the second term spb, p must also divide the LHS of the equation; i.e., b.
There is a special problem involving 1 for the factorization. Unity should not be included for the factorization because any power of unity could be included spoiling the matter of uniqueness. On the other hand it is desirable to included the factorization of unity itself as 1=1, but not as 1=1^{n} for any integer value of n.
Proof:
Let r be any nonzero integer. If r is negative then it can be expressed as (−1)*q where q is a positive integer. If q is prime
the theorem is satisfied. If q is not prime then it is the product of two integers, say m*n, where m<q and n<q.
If any number less than q can be expressed as a product of primes then in particular m and n can be so expressed. Then their poduct q is a product of primes. Since the theorem is true for q=2, by Induction Theorem 2 any integer can be expressed as the product of primes.
Suppose there is an integer q which has two different factorizations, say
where the r_{i} for i=1,…n and the s_{j} for j=1,…m are positive primes. Therefore the (±1) term must be the same for the two factorizations. Any prime on the left, say r_{i}, must divide one of the factors on the right, say s_{j}. But r_{i} and s_{j} are positive and hence this means they must be equal. They can be moved to the left and cancelled out by the Cancellation property of integers. Any other factor on the left can be paired with a factor on the right and cancelled out. When this process is completed there cannot be any factors left on the right. Thus n must be the same as m. This means that the two factorizations have to be the same except for a possible rearrangement of factors.
The standard generalization of the integers is an integral domain. An integral domain is a set of elements S and two operations {+, *} such that for any a,b and c in S:
The integers with ordinary addition and substraction of course constitute an integral domain.
As examples of other integral domains consider systems consisting of ordered pairs of integers (a,b) with the operation of addition as (a,b)+(c,d)=(a+c,b+d) and multiplication as (a,b)*(c,d)=(ac+bdh,ad+cb), where h is any integer which is not a square of an integer. Usually such a system is characterized as consisting of a+b√h. The additive identity is (0,0) and the multiplicative identity is (1,0). The additive inverse of (a,b) is (−a,−b).
Note also that (0,1)*(0,1)=(h,0) and thus, since (0,1)²=(h,0), (0,1) is the square root of (h,0), or effectively the square root of h. This means that (a,b) can be represented as a+b√h. For many purpose this representation is most convenient.
The associativity, communativity and distributivity of such systems follows directly from the associativity, communicativity and distributivity of the integers. Associativity and communativity for addition is trivial, as is communativity for multiplication. Consider three elements of S; (a,b), (c,d) and (e,f) where a, b, c, d, e and f are integers. For establishing the associativity of multiplication it is convenient to represent (a,b) as a+b√h and likewise for (c,d) and (e,f). Associativity of multiplication requires that [(a,b)*(c,d)]*(e,g) be equal to (a,b)*[(c,d)*(e,f)]. This is equivalent to requiring
This is obviously true.
Another example of an integral domain is the set of polynomials with integer coefficients with ordinary addition and multiplication. Let
where the summations start at 0.
The sum of A and B is C such that c_{k}=a_{k}+b_{k}. The product A*B is C such that
where again the summation starts with an index of zero.
Thus the polynomials with integer coefficients when added or multiplied produce another polynomial with integer coefficients. Some of these polynomials can be factored. The ones that cannot be factored are called irreducible rather than prime, but they serve the same role as primes do among the integers.
A polynomial with integer coefficients is denoted as primitive if its coefficients have no common divisor.
Proof:
Let A=Σa_{i}x^{i} and B=Σb_{j}x^{j} be two polynomials with integer coefficients which are
primitive. Let C=A*B; i.e.,
where the summations start at zero.
Assume the product C is not primitive and hence its coefficients have a common divisor q. Let r and s be the indices of the first coefficients of A and B, respectively, that are not divisible by q. Therefore all coefficients of a_{i} for i<r and b_{j} for j<s are divisible by q.
Consider the coefficient c_{r+s} of C. It is equal to
Note that in each terms on the RHS except a_{r}b_{s} one factor is divisible by q. By assumption c_{r+s} is divisible by q. Thus the RHS of the equation must be divisible by q and this can only be if a_{r}b_{s} is divisible by q. This means that at least one of the two factors a_{r} and b_{s} must be divisible by q. This is contrary to the assumption and hence the product C cannot be not primitive; i.e., it has to be primitive.
Not all integral domains possess the property of unique factorization.
Proof:
Consider any polynomial with rational number coefficients a(x),
Let L be the least common multiple of the denominators of the coefficients; i.e., {d_{N}, d_{N-1},…, d_{0}}. (Any common multiple however would work.) Let q_{i}=L/d_{i}. If a(x) is multiplied by L the result is
Thus a polynomial with rational number coefficients is equivalent to a polynomial with integer coefficients.
where N, the degree of a(x) is less than M, the degree of b(x).
Then b(x) can be represented as
where r(x) is a polynomial with rational number coefficents and has degree less than or equal to (M-1).
Proof:
Let c=b_{M}/a_{M}. Then
b(x)−c*x^{M-N}*a(x) = 0*x^{M} + (b_{M-1}−c*a_{M-1})x^{M-1} + …
(b_{0}−c*a_{0})<.
The RHS of the above has degree of (M-1) or less.
Let r(x) equal b(x)−c*x^{M-N}*a(x) and hence
where q(x) and r(x) are polynomials with rational number coefficients.
Proof:
In the first application of the procedure of Lemma 1
a term of degree (M-N) is created and hence the degree of the dividend polynomial q(x) is of degree (M-N). Thus q(x) has to be of
degree (M-N).
If the procedure of Lemma 1 is repeated on b(x) j times the polynomial of degree (M-j). This process can continue as long
as (M-j) is greater than or equal to N; i.e., until M-j=N and thus j=M-N.
The process continues
until the degree of the remaining polynomial is equal to that of the dividing polynomial a(x). Thus the remainder
polynomial can be of degree one less than that of the dividing polynomial a(x). This means that the degree of r(x)
is less than or equal to (N-1).
Proof:
Since S is nonempty it must contain at least one element. The elements of S are ordered by their degrees and so there is a minimum degree,
say d.
Let a(x) be an element of S of minimum degree. Consider any element of S, b(x). By the Factorization Theorem there exist polynomials
q(x) and r(x) such that b(x)=q(x)a(x)+r(x), where r(x) is either the zero polynomial or a polynomial of degree less than a(x). Since a(x) is of minimum
degree a(x), r(x) must be the zero polynomial. Thus b(x) must be a multiple of a(x).
There are more than one polynomial of minimum degree because any constant multiple of a(x) is of the same degree as a(x). But these are the only such elements of S. Suppose c(x) is an element of minimum degree of S. Then there exist q(x) and r(x) such that c(x)=q(x)a(x)+r(x) where r(x) is either the zero polynomial or a polynomial of degree less than a(x). So c(x) must be a multiple of a(x) and since c(x) and a(x) are of the same degree q(x) must be a constant
Proof:
The sum of any two elements of S is also a linear combination of a(x) and b(x) and likewise for their difference. Furthermore any
multiple of a linear combination of a(x) and b(x) is also a linear combination. Thus, by the previous theorem, there exists an element
d(x) of S of minimum degree. Since d(x) is an element of S it is a linerar combination of a(x) and b(t); i.e., there exist
polynomials s(x) and t(x) such that
Furthermore a(x) and b(x) are themselves member of S and hence d(x) divides them.
A polynomial a(x) with coefficients from field F is irreducible if it cannot be factored into the product of polynomials with coefficients from field F. Thus the polynomial x²+1 is irreducible over the field of real numbers but reducible over the field of complex numbers because it is equal to (x+i)(x−i). Likewise x²+2 is irreducible over the field of rational numbers but reducible over the field of real numbers to (x+√2)(x−√2).
Proof:
Consider a(x) first. Since p(x) is irreducible the greatest common divisor of p(x) and a(x) is either p(x) or 1. If the
greatest common divisor of p(x) and a(x) is p(x) then the theorem is satisfied. If the greatest common divisor of p(x) and a(x) is 1
then, by the theorem concerning greatest common divisors of polynomials, there exist polynomials s(x) and t(x) such that
This equation can be multiplied by b(x) to give
On the RHS of this equation, p(x) obviously divides the first term b(x)s(x)p(x). Since p(x), by hypothesis, divides a(x)b(x) it divides the second term and thus divides the LHS b(x).
A monic polynomial is one in which the coefficient of the highest power is unity. For polynomials with coefficients from a field any polynomial can be made monic by multiplying through by the multiplicative inverse of the coefficient of the highest power.
Proof:
Let a(x) be any polynomial over F. If a(x) is a constant or a polynomial irreducible over F then the theorem is fulfilled trivially.
Suppose a(x) is equal to b(x)c(x).
Now the conditions for the Second Induction Theorem can be set up. First of all any polynomial of degree one satisfies the theorem trivially. Now suppose that the theorem is true for any polynomial of any degree less than n. Let w(x) be any polynomial of degree n. If w(x) is irreducible then the theorem is satisfied. Suppose w(x) is not irreducible and is equal to g(x)h(x). If g(x) and h(x) are polynomials of degrees k and n-k, say
Then
and thus w(x)=g(x)h(x) satisfies the theorem. By the Second Induction Theorem the proposition is true for all polynomials.
Now consider the matter of uniqueness. Suppose a(x) is represented by two factorizations, dΠp_{i}(x)) and eΠq_{j}(x). Since the two factorizations are of monic polynomials the leading coefficient of a(x) must be equal to both d and e and hence they must be equal to each other. Since p_{1} divides a(x) it divides Πq_{j}(x). By the Divisibility Theorem for polynomials p_{1} must divide one of the factors q_{j}. But each of those factors is irreducible it means that one of those factors must be equal to p_{1}. That factor and p_{1} can be cancelled out. The same argument can be repeted with p_{2} and so forth until all factors are cancelled out. Thus there is a one-to-one correspondence of the irreducible polynomials in the two factorizations. Thus the factorization of a(x) is unique.
(To be continued.)
Reference:
Garreatt Birkhoff and Saunders MacLane, A Survey of Modern Algebra, Macmillan Co., New York, 1948. *