San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
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.,

• Associativity: For any integers a, b and c
(a+b) + c = a + (b+c)
and
(a*b)*c = a*(b*c).
• Communativity: For any integers a and b
a + b = b + a
and
a*b = b*a.
• Identities:
There exists an additive identity 0 such that for any integer a, a+0=a
and
a multiplicative identity l such that for any integer a, a*1=a.
• Additive Inverses: For any integer a there exists an integer x such that a+x=0. This x is denoted as −a.
• Multiplicative Cancellation: While multiplicative inverses do not exist except for 1, it is true that if ca=cb and c is nonzero then it follows that a=b.

In addition to the above algebraic properties of integers it is also true that integers have an ordering, <, which has the properties of:

• Transitivity: if a<b and b<c then a<c.
• Additive augmentation: if a<b then (a+c)<(b+c)
• Multiplicative augmentation: if a<b and 0<c then ca<cb.
• Well Ordering: Every nonempty set of positive integers (any a such that 0<a) contains a smallest integer.

## Induction Theorems

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.

• Induction Theorem 1: Let P be a proposition concerning integers and let P(n) be that proposition for the integer n. Suppose P(1) is true. Further suppose the truth of P(k) implies the truth of P(k+1), then P(n) 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 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.

• Induction Theorem 2: Let P be a proposition concerning integers and let P(n) be that proposition for the integer n. Suppose P(1) is true. Further suppose that for any integer m the truth of P(k) for any k less than m implies the truth of P(m), then P(n) 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.

## Some Fundamental Lemmas Concerning Integers and Sets of Integers

• Lemma on Integer Sets Closed Under Addition and Subtraction: A nonempty set S of integers which is closed under addition and subtraction is either the singleton set {0} or contains a least positive element h and consists entirely of all multiples of this h.

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.

• Lemma on linear combinations of two integers: The set of all linear combinations is closed under addition and subtraction and there exists a positive integer h such that any linear combination of a and b is equal to a multiple of h. Furthermore this h is a common divisor of a and 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 z1 and z2 of S

#### z1+z2 = j1a+k1b + j2a+k2b = (j1+j2)a + (k1+k2)b

Thus (z1+z2) belongs to S. Likewise (z1−z2)=(j1−j2)a+(k1−k2)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.

• Lemma on the greatest common divisor of two integers: For the greatest common divisor g of two integers a and b there exists two integers r and s such that

#### g = ra + sb

Proof:
By the previous lemma there exists a least positive element h of the set of linear combinations of a and b; i.e.,

#### h = ja + kb

By definition g is a multiple of h, say g=mh. Thus

#### g = mja + mkb

Thus there exist integers r and s such that g=ra+sb.

• Lemma on a prime dividing a product of integers: If p is a prime and p divideds a*b then p divides a or b.

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

#### 1 = ra + sp

This equation may be multiplied by b to give

#### b = rab + spb

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.

## Unique Factorization

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=1n for any integer value of n.

• Fundamental Theorem of Arithmetic: Any nonzero integer which is not ±1 can be expressed as (±1) times a product of positive prime numbers greater than unity. The set of primes and their powers are unique to the integer.

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

#### q = (±1)r1*r2…*rn = (±1)s1*s2…*sm

where the ri for i=1,…n and the sj 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 ri, must divide one of the factors on the right, say sj. But ri and sj 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.

## Integral Domains

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:

1. For any a and b in S (a+b) and (a*b) belong to S.
2. Both + and * are associative; i.e., (a+b)+c=a+(b+c) and (a*b)*c=a*(b*c).
3. Both + and * are communicative; i.e., a+b=b+a and a*b=b*a.
4. Multiplication is distributive over addition; i.e., a*(b+c)=a*b+a*c.
5. There exists additive and multiplicative identities; i.e., a 0 such that for all a in S a+0=a and a 1 in S such that for all a a*1=a.
6. For each element a in S there exists an additive inverse; i.e., an x in S such that a+x=0. The additive inverse of a is denoted as −a.
7. Cancellation holds for multiplication; i.e. if ca=cb then a=b.

## Examples of Integral Domains

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

#### [(a+b√h)*(c+d√h)]*(e+f√h) = (a+b√h)*[(c+d√h)*(e+√h)]

This is obviously true.

Another example of an integral domain is the set of polynomials with integer coefficients with ordinary addition and multiplication. Let

#### A = Σaixi B = Σbjxj C = Σckxk

where the summations start at 0.

The sum of A and B is C such that ck=ak+bk. The product A*B is C such that

#### ck = Σaibk-i

where again the summation starts with an index of zero.

## Polynomials with Integer Coefficiens

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.

## Primitive Polynomials

A polynomial with integer coefficients is denoted as primitive if its coefficients have no common divisor.

• The product of two primitive polynomials is primitive.

Proof:
Let A=Σaixi and B=Σbjxj be two polynomials with integer coefficients which are primitive. Let C=A*B; i.e.,

#### Σckxk = (Σaixi)*(Σbjxj),

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 ai for i<r and bj for j<s are divisible by q.

Consider the coefficient cr+s of C. It is equal to

#### cr+s = a0br+s + a1br+s-1 + … arbs + … ar+sb0

Note that in each terms on the RHS except arbs one factor is divisible by q. By assumption cr+s is divisible by q. Thus the RHS of the equation must be divisible by q and this can only be if arbs is divisible by q. This means that at least one of the two factors ar and bs 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.

## Unique Factorization of Polynomials

Not all integral domains possess the property of unique factorization. ## Polynomials with Rational Number Coefficients

• Lemma: Any polynomial with rational number coefficients is equivalent to a polynomial with integer coefficients.

Proof:

Consider any polynomial with rational number coefficients a(x),

#### (nN/dN)xN + (nN-1/dN-1)xN-1 + … + (n/d0)

Let L be the least common multiple of the denominators of the coefficients; i.e., {dN, dN-1,…, d0}. (Any common multiple however would work.) Let qi=L/di. If a(x) is multiplied by L the result is

#### qNxN+qN-1xN-1+… + q0

Thus a polynomial with rational number coefficients is equivalent to a polynomial with integer coefficients.

## Factorization of Polynomials

• Lemma 1: Let a(x) and b(x) be two polynomials with rational number coefficients, say

#### a(x) = ΣaixN-i b(x) = ΣbixM-i

where N, the degree of a(x) is less than M, the degree of b(x).

Then b(x) can be represented as

#### b(x) = a(x)*cxM-N + r(x)

where r(x) is a polynomial with rational number coefficents and has degree less than or equal to (M-1).

Proof:
Let c=bM/aM. Then b(x)−c*xM-N*a(x) = 0*xM + (bM-1−c*aM-1)xM-1 + … (b0−c*a0)<.

The RHS of the above has degree of (M-1) or less.

Let r(x) equal b(x)−c*xM-N*a(x) and hence

#### b(x) = c*xM-N*a(x) + r(x)

• Lemma 2: If a(x) and b(x) are polynomials with rational number coefficients and the degree of b(x), M, is greater than the degree of a(x), N, then b(x) can be expressed as

#### b(x) = q(x)*a(x) + r(x)

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).

## Theorems Concering Factorization of Polynomials

• Let S be a set of polynomials such that the sum and difference of any two elements of S also belong to S. Furthermore the product of any element of S by any polynomial with rational number coefficients also belong to S. (Such elements are called multiples of an element of S.) For the S to be nonempty it must consist of all multiples of an element of S of minimum degree.

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

## Linear Combinations Of Polynomials Theorem

• Let a(x) and b(x) be two polynomials. Consider the set S of all linear combinations of a(x) and b(x); i.e., all s(x)a(x)+t(x)b(x) where s(x) and t(x) are polynomials. By the theorem concerning sets of polynomials closed under addition, subtraction and multiplication there exists a polynomial of minimum degree d(x) such that all elements of S are multiples of d(x). This means that d(x) is a linear combination of a(x) and b(x). Furthermore d(x) divides a(x) and b(x).

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

#### d(x) = s(x)a(x)+t(x)b(x)

Furthermore a(x) and b(x) are themselves member of S and hence d(x) divides them.

## Irreducibility of Polynomials

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).

## Divisibilty concerning Polynomials

• Theorem: If p(x) is irreducible over the field F then if p(x) divides a(x)b(x) then either p(x) divides a(x) or p(x) divides b(x).

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

#### 1 = s(x)p(x) + t(x)a(x)

This equation can be multiplied by b(x) to give

#### b(x) = b(x)s(x)p(x) + t(x)a(x)b(x)

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).

## Monic Polynomials

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.

## The Unique Factorization of Polynomials

• Theorem on the Unique Factorization of Polynomials: Any polynomial with coefficients from the field F can be expressed as a constant times the product of polynomials irreducible over the field F. Furthermore the factorization is unique except for the order of the irreducible polynomials.

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

#### g(x)h(x) = (dΠpi(x))(eΠqj(x)) = d*e[Πpi(x))(Πqj(x))

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Πpi(x)) and eΠqj(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 p1 divides a(x) it divides Πqj(x). By the Divisibility Theorem for polynomials p1 must divide one of the factors qj. But each of those factors is irreducible it means that one of those factors must be equal to p1. That factor and p1 can be cancelled out. The same argument can be repeted with p2 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. *