main page

ADDITIONAL MATERIAL

Addition of inequalities

For any natural numbers a,b,c,d,     if a<b and c<d  then  a+c<b+d.

Recall that a number u is less than a number v if u is part of a sum that is equal to v:   v = u + z.
Since a<b then for some natural number x,   b = a + x. Since c<d then for some natural number y,   d = c + y. These equations in x and y can be added:   b + d = (a + c) + (x + y)
But this is of the form   v = (u) + (z)    which is equivalent to    u < v
Therefore:   a + c < b + d.

By reversing the direction of the inequality signs, a similar proof exists for
For any natural numbers a,b,c,d,     if a>b and c>d   then  a+c>b+d.

Return to main page


Combining Two Collections with Some Objects in Both

A school offers two foreign languages, Spanish and French. In the Spanish classs are 9 students, and in the French class are 8 students. How many students in the school are taking a foreign language? Take students from both classes, put them in a row in any order, and count them:
S   F    S   F    S   F    S   F    S   F    S   F    S   F    S   F    S
where S and F are students taking Spanish and French respectively. The problem is not completely stated. It is assumed that no student is taking both languages. A slightly different problem arises if there are 4 students taking both languages. Then the above row might become:
S   F  (SF)   S   F    S   F   (SF)   S   F  (SF)  (SF)  S
Here (SF) denotes a single student taking both languages. Notice that there are still 9 S's and 8 F's, but that the contents of the parentheses ( ) are counted twice when forming the sum 9 + 8. Therefore, it is necessary to take one from each of those 4, that is, form the computation 9 + 8 - 4 = 13, which is the correct number of students (separated by spaces) in the row this time.

(Addition law for counting) To find the total (combined) number of objects of two types, add the number of objects of the first type to the number of objects of the second type and subtract the number of objects that are of both types.


Addition of Infinity ω + ω = 2ω

A simple process shows how to find the sum
ω + ω
where ω is the number of positive integers. Count out all positive integers and paint them red. Count out another collection of positive integers and paint them green. (Hopefully there is enough paint!) Then there are no numbers that are both red and green. This makes the two copies of integers distinct. Form a horizontal row by putting the green numbers in between the red numbers.
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 .........
All the numbers in this infinite row can be counted (with black numbers):
1 <-> 1,  2 <-> 1   3 <-> 2,  4 <-> 2   5 <-> 3,  6 <-> 3   7 <-> 4,  8 <-> 4   9 <-> 5,  10 <-> 5   11 <-> 6,  12 <-> 6  
13 <-> 7,  14 <-> 7   .....   99 <-> 50,  100 <-> 50   .....   999999 <-> 500000,  1000000 <-> 500000   .....
In general,   odd n <-> (n+1)/2  and   (even) n <-> n/2.

The conclusion: ω + ω = ω. An infinite number are not like a finite number. Add it to itself and the sum is equal to itself again. Logic dictates this. This discussion also supports the statement   2ω = ω. It is possible to extend the discussion to support   3ω,   4ω,    ... ,   nω, ... . In the later chapter on relations in the section on one-to-one correspondences, the expression   ω x ω   is discussed.


Transitive law of being a factor

For any natural numbers u,v,w, if u is a factor of v, and in turn v is a factor of w, then u is a factor of w. In symbols, if u|v and v|w then u|w.
Since u|v, u is one term of a product of natural numbers that is equal to v. Therefore, for some natural number x, ux = v. Similarly there is a natural number y so that vy = w. In this last equation replace v by its equal ux to get uxy = w. By the associative law for multiplication, xy can be considered a single term: u(xy) = w. Therefore, u is a factor of w.


Pairs of Factors and Limits

It can be proven using the well ordering principle that 1 is the smallest positive integer. But it is an accepted fact in this discussion. But the fact that no factor of a positive integer can be larger than that positive integer is proven here.

Suppose k is a factor of a positive integer m. If k = m, then k is not larger than m.

Suppose k is not the same as m. As a factor k is part of a product nk = m. Then m = k + (n-1)k. Then k is part of the whole m and must be smaller than m. (Technically speaking, n is not equal to 1, so that n-1 is not zero, which has not yet been introduced into the number system.)
------------
If k is a factor of positive integer m then it remains to prove that the quotient m/k is also a factor of m. Since k is a factor of m then k is part of a product of positive integers equal to m: m = nk. Then n = m/k.


Complete factorization of any natural number

A complete factorization of a natural number n is a product of primes without repeats, where each prime may be raised to powers (natural numbers)   n = pa x qb x ... . where p,q,.. are primes and a,b,... are natural numbers. For convenience, primes   p,q,.. are arranged in increasing order: p < q < ...

For example, the number 34425 ends in 5, so 5 must be a factor:

34425 = 5 x 6885
and 5 must be a factor of 6885:
34425 = 5 x 5 x 1377
Since 1377 is not even nor ends in 5, try dividing by 3:
34425 = 5 x 5 x 3 x 459
Try 3 again:
34425 = 5 x 5 x 3 x 3 x 153
Try 3 again:
34425 = 5 x 5 x 3 x 3 x 3 x 51
Try 3 again:
34425 = 5 x 5 x 3 x 3 x 3 x 3 x 17
But 17 is a prime and the breaking down process stops here. Therefore, the complete factorization of 34425 is 34 x 52 x 17.

*(The Fundamental Theorem of Arithmetic) Every natural number larger than 1 has a unique complete factorization into powers of primes.

For a computer program that computes the complete factorizations of natural numbers click here


gcd and lcm from complete factorizations of two natural numbers

Recall the law of addition of (natural number) exponents: um un = um+n. Let s = m+n. This means that both   um   and   un   are factors of   us   because their product is equal to us.

This idea can be used with the powers of prime factors of two natural numbers larger than 1. The best explanation comes with an example. The complete factorizations of two numbers 172872 and 111132 are:

172872 = 23 x 32 x 74,      111132 = 22 x 34 x 73
The first terms of each factorization are 23 and 22. Choose the smaller term, that is, the term with the smaller exponent. It is 22. It is a factor of both natural numbers 172872 and 111132. Any power larger than 22 would not be a factor of 111132.

Do the same for the next terms in each factorization, 32 and 34. The smaller of 32 and 34 is 32.
Finaly choose the smaller of 74 and 73 which is 73.

Assemble these three new terms to get:   gcd(172872,111132) = 22 x 32 x 73 = 12348
The choice of smaller of pairs of terms in each decomposition guarantees that 12348 is a divisor of both numbers 172872 and 111132. Moreover, by choice of lower powers of prime factors, 12348 is the largest common factor.

The dual of choosing the smaller exponent is choosing the larger exponent. The dual of gcd is lcm. This suggests a similar method for constructing the lcm, namely choosing the larger of corresponding terms.
The larger of 23 and 22 is 23.
The larger of 32 and 34 is 34.
The larger of 74 and 73 is 74.
These three choices of larger form the product:   lcm(172872,111132) = 23 x 34 x 74 = 1555848.


It may happen that a prime factor in a complete factorization does not have a written exponent:   4704 = 25 x 3 x 72. In order to compare exponents, the prime factor 3 will need an exponent. But 3 = 31.

It may happen that two natural numbers may have different prime factors (and some may be the same). For example,

27783 = 34 x 73       3920 = 24 x 5 x 72
To address this situation, zero exponents will be introduced here prematurely. In the next chapter on non-negative integers it will be shown that any natural number raised to the zero power is equal to one:   u° = 1. Therefore, missing prime factors can be written with exponent zero. Therefore, the products of the prime factors may be written:
27783 = 2° x 34 x 5° x 73       3920 = 24 x 3° x 51 x 72
It is easy now to choose the smaller and larger exponents on the prime factors 2,3,5,7 to get:
gcd(27783,3920) = 2° x 3° x 5° x 72 = 1 x 1 x 1 x 72 = 49,      lcm(27783,3920) = 24 x 34 x 51 x 73 = 2222640



The product of the gcd and lcm of two natural numbers is equal to the product of those numbers

The following paragraphs [A] and [B] are the "tecnhical definitions of gcd and lcm:

[A] The greatest common divisor (gcd) of two given natural numbers m,n is a natural number d satisfying the following two conditions:
   (a)   it must be a divisor of both given numbers:   d|m   and  d|n;
   (b) any natural number x that is a divisor of both given numbers must be a divisor of the greatest common divisor:    if   x|m   and  x|n  then  x|d.
Notation: d = gcd(m,n).

[B] The least common multiple (lcm) of two given natural numbers m,n is an natural number k satisfying the following two conditions:
   (a)  it must be a multiple of both given numbers:   m|k   and  n|k;
   (b) any natural number x that is a multiple of both given numbers must be a multiple of the least common multiple:
            if   m|x  and  n|x  then  k|x.
Notation: k = lcm(m,n).

Let d = gcd(m,n)    and    k = lcm(m,n).
The theorem can be expressed as:              dk = m x n .


The proof is in two parts.

First part of the proof:   dk | mn     product of gcd and lcm divides the product of the natural numbers.

By [A] the quotient   n/d   is an natural number. Then the product   m (n/d) = mn/d   is also an natural number, which means
(*)             m | mn/d.
Similarly, by [A] the quotient   m/d    is a natural number. Then the product   n (m/d) = mn/d   is also an natural number and
(**)            n | mn/d
By (*) and (**) the natural number   mn/d   is a common multiple of both m and n. By [B]   least common multiple    must divide all such multiples. Therefore
                    k | mn/d.
By theorem [ ]
(***)             kd |mn.


Second part of the proof:   mn | dk     the product of the natural numbers divides the product of gcd and lcm.

Since mn is a multiple of both m and n, by [B] the least common multiple must be able to divide completely into it, that is, the quotient mn/k is an natural number. According to [B] both quotients    k/m   and k/n    are natural numbers. The product of any two natural numbers is a natural number (closure) so

n = (mn/k) (k/m)       and       m = (mn/k) (k/n)
Therefore      mn/k | n       and       mn/k | m.
This means that the natural number expression   mn/k   is a divisor of both n and m. By [A] it is a divisor of the greatest common divisor, that is mn/k | d. By theorem [ ]
(****)             mn | kd

(***) and (****) show that   kd   and   mn    divide each other. By theorem [ ] they must be equal.


A numerical method showing the above theorem about the product of gcd and lcm

The method of compmlete factorization can be used to find the gcd and lcm of two natural numbers 3528, 111132. The complete factorizations of these two numbers are:
3528 = 23 x 32 x 72      111132 = 22 x 34 x 73
Now choose the smallest exponent of 2, the smallest exponent of 3 and the smallest exponent on 7 to get:
22 x 32 x 72 = gcd(3528,111132) = 1764,         23 x 34 x 73 = lcm(3528,111132) = 222264
The second expression is obtained by selecting the larger of the exponents on the prime factors.

The product of the numbers 3528 and 111132 is equal to 25 x 36 x 75 = 392 073 696. The product of gcd(3528,111132) and lcm(3528,111132) = 25 x 36 x 75 = 1764 x 222264 = 392 073 696.