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. **************
(To be continued.) *