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 z₁ and z₂ of S

z₁+z₂ = j₁a+k₁b + j₂a+k₂b = (j₁+j₂)a + (k₁+k₂)b

Thus (z₁+z₂) belongs to S. Likewise (z₁−z₂)=(j₁−j₂)a+(k₁−k₂)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=1ⁿ 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)r₁*r₂…*r_n = (±1)s₁*s₂…*s_m

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.

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 = Σa_ixⁱ
B = Σb_jx^j
C = Σc_kx^k

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

c_k = Σa_ib_k-i

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.

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=Σa_ixⁱ and B=Σb_jx^j be two polynomials with integer coefficients which are primitive. Let C=A*B; i.e.,

Σc_kx^k = (Σa_ixⁱ)*(Σb_jx^j),

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

c_r+s = a₀b_r+s + a₁b_r+s-1 + … a_rb_s + … a_r+sb₀

Note that in each terms on the RHS except a_rb_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_rb_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.) *