Chapter 2
Number Systems: Natural Numbers

Section 1   The Natural Numbers and Addition

The oldest and most basic of all our number systems is the system of natural numbers. (They are also called whole numbers). A rigorous description of them is given by assumptions called the Peano Postulates. The approach to the natural numbers in this chapter does not start with those postulates, but uses some of the familiar properties and supplements them with some fundamental but reasonable principles. Intuitively speaking, the list of all natural numbers will be "built" one number after another.

One major purpose for natural numbers is to indicate quantity. In these discussions the numbers are used to indicate by counting how many objects are being considered in a collection. To make the circumstances more familiar, suppose the collection is in a bag. A collection with just a single object in a bag has the number 1 associated with it. In some sense it is a starting place. Another object is added to the bag, and now the number 2 is associated with the collection. Then by adding repeatedly another object to the bag more natural numbers are created to indicate how many objects are in the growing collection. The reader is already familiar with the symbols used to indicate the numbers. After some number has been placed in a list, usually written horizontally, the next number is placed to the right of it. (In this chapter a list is indicated by the symbols {   } placed before and after the sequence of numbers, separated by commas.

Suppose the process of increasing the number of objects in the collection stops. The numbers that have been created before the stop can be written in the form of a list. For example if the production stops immediately after 9 then a short list has been formed:

(List of the first 9 natural numbers) {1, 2, 3, 4, 5, 6, 7, 8, 9}
This list is given the name N₉.

The generation of the list N_n starts at 1 and stops at the number n. Then N_n is called the list of the first n natural numbers. Such a list is called finite.

The finite list N₁₂ supplies the numbers on the face of a clock. The finite list N₂₄ supplies the numbers on the face of a full day military clock.

We live in a world of finite numbers. (It is a philosophical question whether there exists infinitely many objects somewhere in the universe.) If any collection of objects is counted, there is a last number. If all the grains of sand on a beach are counted, there would be a number to indicate the number of grains. If all the molecules of water in the oceans are counted, there would be a last molecule in the count. These are very large numbers. But there are numbers larger than these. The number

A different approach is needed. The repeated addition of objects to a collection in a bag suggests a method. 1 is definitely a natural number. Then, intuitively, a chain reaction starts, repeatedly using the "immediate successor" idea, and running through all the natural numbers instantly (no time is involved because this is a theoretical idea, not a physical process). This idea is expressed in the following:

[1.1] (Inductive definition of all natural numbers) The list N of all natural numbers is defined as follows:
   (a) the natural number 1 is in the list, and
   (b) any natural number already in the list guarantees somehow that the next natural number, the immediate successor, is also in the list.

There is a familiar geometric representation of the natural numbers. On some line (usually horizontal) certain points will be selected to correspond with natural numbers. To see them better they will be indicated by short vertical line segments like | called markers. Select any point and mark it. It is the point correponding to 1. (The part of the line to the left of the marker may be erased to get a "half-line") To the right select a second point and mark it. That new point corresponds to 2. Using the same distance between the markers for 1 and 2, mark a new point to the right of 2. It corresponds to 3. In general, after the marked point corresponding to the natural number n, locate a point to the right of it (using the same distance between markers for 1 and 2) to locate the immediate successor to n. The new point will correspond to the natural number n+1. In theory, this process of locating points for immediate successors never stops in order to obtain the geometric representation of all natural numbers.

The half-line to the left of 1 was removed. This means that the list N starts with 1. There are no natural numbers to the left of 1. Later the left half line will be restored and points corresponding to more familiar numbers will be created there. The right half line shows that there are spaces between the marked points. (For this reason the markers locate discrete points.) This suggests that there are possibly other numbers like fractions, which are not "whole", to correspond to points between two adjacent markers.

Based upon this definition [1.1] is a method of proof called mathematical induction. It is discussed in section 3 of this chapter.

By entering numbers into a list of natural numbers to the right of numbers already there, the numbers in the list become larger. Going to the left, the numbers become smaller. Obviously, 1 is the smallest natural number.

[1.2] (Principle of Linear Order*) For any pair of unequal natural numbers, a number must be less than the other. Equivalently, a number must be greater than the other.

This principle allows the natural numbers to be assigned to consecutive points on a horizontal straight line, starting with 1 and going to the right. By this assignment a smaller number is located to the left of a larger number. A larger number is located to the right of a smaller number. But those readers who are familiar with complex numbers have seen a system in which some numbers cannot be compared for size: It cannot be said which of the numbers 3 + 4i and 4 + 3i is larger than the other. The points for all complex numbers is a plane, not a line. The complex numbers are not linearly ordered.

This idea of linear order can be applied in reality. Suppose some 100 objects of different shapes and sizes are to be moved from one warehouse to another by trucks. An economy of space on the trucks can be realized if the objects are taken out in a certain order and loaded. Before moving them a workman marks the objects with natural numbers from 1 to 100 to show that order of transfer. For any two objects, the object with the smaller number is moved first.

From using the natural numbers a person is aware that they are different from fractions and decimal numbers, at least in appearance. But they are different in nature. It is meaningful to say that the number 5 is next to the number 4. But it is not meaningful to say that the number 3/8 is next to the number 2/8 because there are many numbers between them, including the number 5/16. Between any two fractions is another fraction, their average. The same is true of real decimal numbers.


Quite often collections of natural numbers may or may not include all of them. Each of the following is a list containing some natural numbers:

[1.3] (Well Ordering Principle of N) Every (non-empty) list of natural numbers has a smallest natural number in it.

[1.4] (Counting by Association) To count the number of objects in a collection, associate with each object in the collection a single natural number, starting with 1 and continuing to the right one number at a time, so that every object in the collection has a single natural number from N_n associated with it. The collection is said to have (exactly) n objects and to be finite. If the counting process never stops then all the natural numbers in N in are involved, and the collection is said to be infinite.

It is important that counting be a one-on-one process. No object should be counted twice. (Different natural numbers cannot be associated with the same object). Different objects cannot be associated with the same natural number.

In these discussions the letters i,j,k,m,n are often used to denote natural numbers (later integers). The letters x,y,z,w are used to denote any numbers or algebraic expressions.

Each of the finite list N_n has a number n indicating the number of natural numbers are in that list. Some people like to have the symbol ω (the last letter in the Greek alphabet) to indicate the number of natural numbers in the list N of all natural numbers. ω is the first transfinite number introduced in these discussions. N_ω = N. It has some interesting arithmetic peculiarities that go against intuition developed by prolonged use of finite numbers. More discussion is found in the section on one-to-one correspondences in the chapter on relations.


The process of counting allows simple addition of natural numbers. To find the sum 3 + 2, start with a bag with 3 objects in it, and then add 2 more objects to the bag and then count the total in the bag to get 5. Theoretically, this process could produce a table of addition of various pairs of natural numbers. For any two natural numbers m and n there is a single natural number m+n, which is their sum. Addition is called a binary operation because it "operates" on two numbers. This laborious, physical method of finding sums of pairs of natural numbers is replaced by rules which humans memorize and use to do additions. Even faster, pairs of natural numbers of limited size may be added using mechanical or electronic devices.

[1.5] (Physical method of addition*) To find the sum n+m of any two natural numbers n and m, start with n distinct objects in a bag, to the content of the bag add m distinct objects, and count the objects in the bag.

It is customary to use the term "sum" to mean the form n + m as well as the numerical value that is produced from the addition. Both 3 + 4 and 7 are sums. The process of obtaining 7 from 3 + 4 is called b>addition.

The familiar method of addition is the basis of addition mentioned here. Theoretically, it is always possible to take any two numbers and find a number that is their correct sum. There exists a natural number that equals the sum

[1.6] (Closure of the addition operation*) For any two natural numbers there will always exist a third natural number that is equal to their sum.

The numbers being added together are called addends.

The system of all natural numbers and the operation of addition form an additive system. It is a closed additive system because of [1.6]. But the collection {8,12} of just the two numbers 8 and 12 with addition does not form a closed additive system because the sum 8 + 12 is not in this system. Suppose bag A has 2 objects in it and bag B has 3 objects in it. If the content of bag B is poured into bag A, then 3 objects will be added tto the content of A, and the number of objects in bag A will be 2 + 3. But instead if bag A is poured into bag B, then 2 objects will be added to the content of bag B, and the number of objects in bag B will be 3 + 2. No objects are lost and no extra objects are added. Therefore, the number of objects is 5, all in one bag either way. The commutative law guarantees that 2 + 3 = 3 + 2.

[1.7] (The commutative law*) The sum is the same if any pair of numbers are added in either order
For any pair of numbers m,n,   m + n = n + m.

A formal proof of [1.7] involves a careful use mathematical induction and is beyond the scope of any discussion in these volumes. However, a simple supporting discussion may be made by replacing 2 by m and 3 by n in the paragraph before [1.7].

There are other systems in which a form of addition has been defined. It is customary to consider all additive systems to be commutative , otherwise do not use the plus sign (+) as the operation symbol.

The operation (+) of addition acts only on two numbers at a time. The placing of counted objects into a bag provides a physical method for extending addition to more than two counted collections of objects. The sum 2 + 3 + 4 means to add to an empty bag, two objects, three objects, and four objects. There will be 9 objects in the bag. The same sum is obtained in another way. First add 2 and then 3 objects to a second bag. The second bag contains 5 objects. Now pour the contents of the second bag and 4 objects into the first bag at the same time. The first bag will contain all 9 objects. The parentheses indicate the use of the second bag:   (2 + 3) + 4 = 9. They also indicate that the addition of 2 and 3 is done before the addition involving 4.

(Addition of three natural numbers) To add three numbers, add the first two, then add that sum to the third number.
Notation: The sum of k,m,n = (k+m) + n.

To add four numbers, find the sum of the first three, then add that sum to the fourth number. To add five numbers, find the sum of the first four and then add that sum to the fifth number. This (inductive) process applies to any collection of numbers. But the addition operation still involves only two numbers at a time.

Return now to the sum of three numbers. The sum (2 + 3) + 4 means the first + is to be done first to get 5 + 4. But 2 + (3 + 4) means that the second + is to be done first to get 2 + 7. Physically, the 3 objects and the 4 objects are placed in the second bag, then the 2 objects and the content of the second bag are placed into the first bag. Since no objects were lost in using the second bag was used either way, the final count is 9 objects in the first bag. The associative law guarantees that (5) + 4 = 2 + (7).

[1.8] (The associative law*) For any three numbers, k, m, n,   (k + m) + n = k + (m + n).

Notice that the (alphabetic) order is the same on both sides of the equation. It is assumed that the physical model using the second bag provides support for the [1.8] because no objects are lost or any extra objects are added. A formal proof of the associative law involves careful use of mathematical induction and is beyond the scope of any discussion in these volumes.

Using both laws [1.7] and [1.8] it can be said that numbers can be added in any order. This fact guarantees that the total cost of all items bought in a store will be the same, no matter in what order the items were selected.

[1.9] The sum of two natural numbers is larger than either natural number. In general, each of two or more natural numbers is less than the sum of all of them.

7 is larger than 4 because 7 = 4 + 3. For the same reason, 4 is less than 7. Each of a,b,c,d representing natural numbers, is less than their sum a+b+c+d.

The definitions [1.10a] and [1.10b] below shift the burden of defining inequalities from positions in the list of all natural numbers to the operation of addition. They both are restatements of [1.9]. They look at the same situation as [1.9] but different ways.

A natural number n is less than a natural number s if and only if n is part of a sum equal to s.

[1.10a] (Less than*) A natural number n is less than a natural number s if and only if s = n + x, where x is some natural number.
Notation: n < s

The expression s = n + x is an equation with unknown x, and with s and x known natural numbers.

A natural number s is greater than a natural number n if and only if s is equal to the sum of of which n is a part:

[1.10b] (Greater than*) A natural number s is less than a natural number n if and only if s = n + x, where x is some natural number.
Notation: s > n From the wording "less than" and "greater than" are dual ideas. And it is not difficult to show that n < s and s > n are equivalent statements.

5 < 12 because it is possible to put some natural number into ( ) and get a true equation 5 + ( ) = 12. There exists a number 7 so that 5 + 7 = 12. But it is impossible to find a natural number to put into ( ) in the expression 9 + ( ) = 6 and make it into a true equation. The sum 9 + ( ) becomes bigger for any natural number placed in ( ).

[1.11a] (Telescope*) If one natural number is smaller than the second, and the second natural number is smaller than the third, then the first positive integer is smaller than the third.

[1.11b] (Telescope*) If one natural number is larger than the second, and the second natural number is larger than the third, then the first natural number is larger than the third.

An intuitive argument for [1.11a] is the following:
In the horizontal list [1.1] of natural numbers, if a is to the left of b, and b is to the left of c then a is to the left of both b and c. This supports the truth of [1.11a]. A similar statement may be made about [1.11b] using "right" in place of "left". (a result of the duality of < and >), replacing the words "left" and "smaller" by "right" and "larger."

A more formal argument for [1.11a] is the following:
Let a,b,c be natural numbers such that   a<b   and   b<c. Then a is a part of whole b, so
(#)                 b = a + some natural number
Similarly:
(##)                c = b + some natural number
Replace the b in equation (##) by the right side of the equation in (#) to get:
                c = a + some natural number + some natural number
The two unimportant natural numbers can be added. This means that a is part of the whole c. Therefore,   a<c.

[1.12a] (Addition of inequalities <*) For any natural numbers a,b,c,d,     if a<b and c<d   then   a+c<b+d.
[1.12b] (Addition of inequalities >*) For any natural numbers a,b,c,d,     if a>b and c>d   then   a+c>b+d.

For proofs of these two statements click here. They can be extended to involve more variables.

[1.13a] (Physical method of limited subtraction of natural numbers*) To find the difference s-n of two natural numbers s and n, where s>n, start with s distinct objects in a bag, remove from the content of the bag n objects.. Then count the objects remaining in the bag..

This subtraction is limited, because a number n greater or equal to s cannot yet be subtracted from s. If this attempted then there is no natural number equal to the result. Therefore subtraction is not a closed operation on natural numbers. In a later section the collection of natural numbers will be expanded into signed integers, and there subtraction will be a closed operation. Subtraction is not associative nor commutative. Yet it will be a useful operation in later sections.

In the situation of 5 - 3, consider 5 as a sum, and 3 as one of the addends. Then the subtraction 5 - 3 produces the other addend 2, so that 5 = 3 + 2. In general, if the natural number s is the sum of an addend n then the other addend is equal to s - n. This is because of the identity s = n + (s - n). Rewrite the identity as (s - n) + n = s, and realize the corresponding physical situation, namely, if n objects are removed of a bag with s objects and then n objects are added back into the bag, the bag will have the original number s of objects.

Now consider finding 5 - 3 as an algebra problem. Let x be the unknnown equal to this difference: 5 - 3 = x. Then 5 has two addends 3 and x. So 5 = 3 + x. Trying x=1, does not work, trying x=2 does work and gives a solution. This more cumbersome method will provide a method for extending subtraction to integers and to some other algebraic system.

[1.13b] (Standard definition of subtraction*) The difference s-n of two natural numbers s and n is that natural number x that satisfies the equation s = n + x.

The statement [1.13b] does not guarantee a solution. 10 + x = 7 has no natural number solution for x (a sum of two natural numbers is larger than either natural number, and the sum 7 is smaller than the addend 10). Therefore the subtraction 7 - 10 cannot be done usiing only natural numbers.

For any pair of distinct natural numbers by [1.2] one must be the larger and the other must be the smaller. Therefore, a limited subtraction is always possible by subtracting the smaller from the larger (larger - smaller). If u and v denote arbitrary but unequal natural numbers, no information is given about which is larger. The subtraction u - v may not be possible because v is the larger. The following is a solution to this problem and makes limited subtraction always possible for distinct natural numbers:

[1.14] (Absolute value of the difference of two unequal natural numbers)
  |u - v| = u - v   if u is the larger;      |u - v| = v - u   if v is the larger.

Examples:   |5 - 3| = 2,   |6 - 9| = 9 - 6 = 3,   |100 - 40| = 60,   |40 - 100| = 60.
Intuitively speaking, absolute value avoids the use of negative numbers. It is widely accepted that distance is not negative. If u and v locate distinct markers on the number line, then |u - v| is the distance between them. (See the discussion just after [1.2].)

Section 2   Multiplication of Natural Numbers

[2.1a] (Physical method of finding a product of two natural numbers) To find the product nm, into an empty bag add m objects and do this adding process a total of n times. The product is equal to the total number of objects now in the bag.

When actual numbers are used for n and m, the form is written n x m. For example 3 x 4. But when letters are used, the product is written nm. It is customary to use the term "product" to mean the form nm as well as the numerical value that is produced from the multiplication. Both 3 x 4 and 12 are products. The process of obtaining 12 from 3 x 4 is called multiplication.

The first (dark black boldface) number in the product is called a coefficient. It indicates the number of times that the second number is added. Actually the second number could be replaced with an algebraic expression w: For example,
  3w   =   w + w + w.
  3(ax + byz)⁵   =   (ax + byz)⁵ + (ax + byz)⁵ + (ax + byz)⁵.

[2.1b] (Algebraic method for evaluating a product*) The product nw of a natural number   n    and a numerical or algebraic quantity   w    is equal to the sum of that quantity   w    repeated n times in the addition process: nw = w + w + ... + w    (Click here to see how math induction [1.1b] can be used to make this definition more exact.) The integer n is called a coefficient of    w.

Finding areas of rectangles by multiplying lengths of adjacent sides suggests a more organized method for evaluating a product of natural numbers. Let the objects being counted small squares. Instead of using repeated addition (linear form) sq sq sq sq + sq sq sq sq + sq sq sq sq and then counting the sq's, use a two-dimensional rectangular form wiith rows of 4 squares under each other, as shown in the adjacent figure, and then count the squares. This suggests that areas of geometric rectangles provide a method to calculate the product of two natural numbers.

[2.1c] (Geometric method for evaluating a product) To find the product   nm   of a natural number n and a natural number m, construct a rectangle with height n and width m. Then count the number of squares (square areas) the rectangle contains.

In addition to the above methods for evaluating a product, an inductive definition can be found by clicking here. However it is advisible to wait until section 3 of this chapter.

(Dual:   for addition:   n + m = m + n)

Mathematical induction can be used to prove this law for natural numbers. However, a simple geometric argument supports it. Draw the rectangle with height m and width n. Then there are mn squares inside the rectangle. Rotate the triangle through 90° Now it is a nm rectangle. The number of squares is the same because the two rectangles are congruent. The figure to the right shows this argument for the product 3x4 = 4x3.

[2.3] (Associative law for multiplication of natural numbers*) For any natural numbers k,m,n,    k(mn) = (km)n.

(Dual:   for addition:   k + (m + n) = (k + m) + n)

Again this law can be proven using mathematical induction. A geometric argument supports it, using a rectangular three dimensional box containing unit cubes whose count = volume. It will not be given here, and the associative law is assumed to be true.

The definition [2.1b] connects multiplication with addition through counting. Since 3 objects plus 2 objects equals 5 objects, it is reasonable that 3w + 2w = 5w, where w is a natural number. (Actually, w may be any numerical or algebraic expression.) Sow (3 + 2)w = 3w + 2w. A generalization of this idea supports the following:

[2.4a] (Right distributive law*) For any natural numbers m,n,w,    (m + n)w = mw + nw.

If there are m objects and n more objects are added then there are a total of (m + n) objects. Consider the number w as an object (perhaps written on a piece of paper). Then mw + nw = (m + n)w.

This time consideer an expression   (u + v) appearing in a sum 3 times:   (u + v) + (u + v) + (u + v).   By definition [2.1b] this sum can be written   3(u + v).   But removing the parentheses and using the commutative and associative laws this repeated sum is equal to   3u + 3v.   Therefore   3(u + v) = 3u + 3v.   A generalization of this idea supports the following:

[2.4b] (Left distributive law for natural numbers*) For any natural numbers u,v,n,    n(u + v) = nu + nv.

Actually, the commutative law makes these two distributive laws logically equivalent. The w in [2.4a] can be repositioned in front of the sum (m + n) and become a coefficient. In some later systems neither distributive can be proven directly from the other using a commutive law.

The number 1 is the smallest natural number. But it also as a special role in multiplication;

[2.5] (Multiplicative identity*) For any natural number n, the product:  1n = n.


In [2.1b] multiplication was introduced as repeated addition. It is possible to have a number repeatedly multiplied by itself. 5²=5x5 = 25, 10³=1000, w² = ww, w³ = www.

[2.6] (Powers*) The n-th power wⁿ of any quantity w is equal to the product of that quantity repeated n times in the multiplication process: wⁿ = ww...w   where w appears in the multiplication process n times. The integer n is called an exponent on w.

[2.7] (1 As exponent*) w¹ = w.

So [2.7] and [2.5] continue the duality between exponents and coefficients.

[2.8] (Associative law for multiplication*) For any natural numbers u(vw) = (uv)w. (Duality: for addition: u + (v + w) = (u + v) + w.)

[2.9] (Exponential law*)   (uv)ⁿ = uⁿvⁿ

This law is the dual of the distributive law [2.4b]. The supporting argument is similar.

[2.10] (Comparison laws*)
  (a)   if u < v then nu < nv
  (b)   if u > v then nu > nv

The proof of (a) is simple. If u < v then there is a natural number x such that v = u + x. Multiply both sides of this equation by n to get nv = nu + nx. Since nx is a natural number nu < nv. The same argument can be made for part (b).

[2.11] (Cancellation law*)
nu = nv implies u = v

The argument for this law directly supports the contrapositive: if u is not equal to v, then nu is not equal to nv.
If u is not equal to v, then by [1.2] (Law of linearity)   u < v or u > v. If u < v then nu < nv by [2.10a], which means that nu is not equal to nv. Similarly if u > v then nu > nv by [2.10b], which also means that nu is not equal to nv.

Since n is a natural number then it cannot be zero. In the next section about integers, this condition n not equal to zero will be explicitly stated. An argument supporting [2.11] will be supplied there.
The use of the commutative law can be used to prove that [b] follows immediately from [a].

Addition and multiplication combine two numbers to produce a sum and product respectively. They are called binary operations. A binary operation combines any two things from a collection and produces a single quantity that is in that same collection (closure). The commutative and associative laws can be stated as
                                              u o v = v o u                                                [commutative law]
                                     u o (v o w) = (u o v) o w                                       [associative law]
where o may be replaced by either the addition or multiplication symbol. In most systems that the reader may encounter, the associative law will hold true. But in some systems the commutative law may not hold true. Discussed later in this volume are systems of functions, and in other volumes matrices, and quaternions, all of which are not in general commutative. It is customary to write an operation that is not commutative as multiplication.

The natural number n is a factor of a number m if there is a natural number that can be placed inside ( ) to make the expression m = n x ( ) become a true equation. A much better way of expressing this is as follows where y = ( ):

[2.12] (Factors and divisors*) A natural number n is a factor or divisor of a natural number m if and only if there exists a natural number y satisfying the equation m = ny    [nk = product of n and y].
Notation: n | m   means   n is a factor of m.

By algebra y = m/n (quotient). However, this fraction which indicates ordinary division, may or may not equal a natural number. The fraction 1212/5 is not. Therefore 3 is a factor of 12, and the fraction 12/3 = 4 is the other factor of 12. But 12/5 is not equal to a natural number.

[2.13] (Test for factor by division) The natural number n is a factor of a natural number m if the fraction m/n is equal to a (whole) natural number. If it is equal, then that natural number is equal to the other factor of m. (The two factors may be equal.) Logically, the statement [2.13] is out of place, because division has not yet been defined. But this premature use of fractions here makes the process of determining whether or not a natural number is a factor very simple and clear.
For a natural number to be a perfect square, the two factors, by definition, are equal. For examp[le, 81 = 9x9. The fraction 81/9 = 9. Therefore, 9 is a factor of 81 and 9 is the "other" factor.
The division m/n can be done more conveniently by electronic devices, such as a calculator.

[2.14] (Multiples*) A natural number m is a multiple of a natural number n   iff   n is a factor of m.

For example,

A duality exists between factor and multiple:     7 is a factor of 21   21 is a multiple of 7.

For any natural number there is a (finite) list of all the natural numbers that are its factors.
    The list of all factors of 12 is   {1,2,3,4,6,12}
    The list of all factors of 40 is   {1,2,4,5,8,20,40}
    The list of all factors of 48 is   {1,2,3,4,6,8,12,24,48}
    The list of all factors of 17 is   {1,17}

Click here to see some facts that reduce the number of fractions to be tested for complete division. There may be much computation even after removal of some of the fractions because many fractions may remain to be tested for complete division. especially if the natural number is very large, such as 9473651. And done by hand or calculator it is easy to miss some of the factors. Click here to find a computer program to produce this list of all the factors of a natural number (within the capacity of the machine, often less than or equal to 4 294 967 291).

By [2.5] 1 is a factor of every natural number. Also every natural number n is a factor of itself. These two numbers, 1 and n must be in every list of all factors. For any natural number n, the numbers 1 and n are called trivial factors of n. Factors not trivial are called non-trivial. In the above lists the non-trivial factors are in darker boldface.

[2.15] (Primes*) A prime is a natural number that is larger than 1 and that has only trivial factors. A number larger than 1 but not a prime is called composite.

The following is a list of all the primes that are less than 100..

It is convenient to use a computer to show that the natural number 2,147,483,647 is a prime. In fact it is the largest prime in many computer systems.

The ancient Greek geometer Euclid proved that the list of all primes is infinitely long. Another ancient Greek, Eratothenes, discovered a method, called a sieve, for finding all primes. Click here to see a discussion of this method. No algebraic formula has yet been invented for finding all the primes. It seems that the primes are distributed randomly among all the natural numbers.

The numbers 42 and 87 are composite. They are not in the list (&). For convenience later, 1 is not allowed to be a prime..

Intuitively speaking, a composite natural number may be "broken down" into smaller pieces, its factors. The composite number 45 can be broken down into factors 9 and 5. A prime cannot be broken down into smaller pieces. The number 17 has only trivial factors, and cannot be broken down into smaller pieces.

Sometimes the factors can be broken down.   45 = 9 x 5 but 9 can be broken down into 3 and 3, so that 45 = 3 x 3 x 5. None of these factors can be broken down further. The number 45 has been broken down into primes and the "breaking down" process stops there. Using exponents, 45 = 3² x 5.

This process of breaking down factors into smaller factors to get prime factors is based on the following theorem:

[2.16] (Transitive property of being a factor*) If a first natural number is a factor of a second natural number, and that second natural number is a factor of a third natural number, then the first natural number is a factor of the third.

For example, 3 is a factor of 12, and 12 is a factor of 84, so 3 is a factor of 84. Click here to see a simple proof of this theorem.

The following is an immediate result of [2.16]

[2.17] (*) If a natural number is not a factor of a second natural number, then no multiple of the first number can be a factor of the second number.

For example 2 is not a factor of 99, then 4,6,8,10,... cannot be factors of 99.

Non-trivial factors of a given natural number are smaller than that number. Usually the smaller the number the easier it is to find its factors, which in turn will be factors of the original natural number. For example it is obvious that 10 is a factor of 560. But 2 and 5 are factors of 10. Therefore 2 and 5 are factors of 560. Dividing 10 into 560 produces 56 which is a factor of 560. Since 56 = 8x7, and 2 is a factor of 8, the prime factors of 56 are 2 and 7. Therefore the list of all prime factors of 560 is {2,5,7}. This discussion shows a method for finding all the prime factors of a natural number.

Every breaking down a natural number into prime factors will produce the same prime factors. But 560 is not equal to the product of its prime factors; because there are composite factors. for example 56.. However 560 = 16x5x7 = 2⁴x5x7. Click here for a brief discussion of complete factorization of any natural number.

In general each number in the list N may be multiplied by any natural number k to produce a new list kN of all multiples of the number k:

[2.18] (Addition of numbers with a common factor) Any common factor of two (or more) natural numbers is a factor of their sum.

Suppose k is a common factor of m and n. Then by definition   m = ku   and   n = kv   for some natural numbers u and v. Now a form of the distributive law is   ku + kv = k(u + v).   Therefore,

The list kN is closed under addition. A collection of numbers not closed under addition would be a defective system in many cases. For example, in the list {4,7} there are just two numbers. It is not closed under addition, because 4+7 = 11 and 11 is not in the list. In fact, the only collections of natural numbers, closed under addition, are all the multiples of some natural number. This fact will be discussed in the next section.

Suppose the coefficients in the collection kN become exponents:

In the collection of powers of some natural number, the product of any two natural number is back in the collection. So the colllection is closed under multiplication.

A collection of numbers not closed under multiplication would be a defective system in many cases. If only 4 and 7 were in some collection, then that collection of just two numbers is not closed under multiplication, because 4x7 = 28 and 28 is not in the collection. In fact, the only collections of natural numbers (having some natural number not 1), closed under multiplication, are all the powers of some natural number.

The following statements are copies from above:
    The list of all factors of 12 is   {1,2,3,4,6,12}
    The list of all factors of 40 is   {1,2,4,5,8,20,40}
The factor 2 is in both lists. The factor 4 is also in both lists. To get the third fraction directly from the first, divide both the numerator 12 and denominator 40 of the first fraction by 4.

A factor (or divisor) is common to two or more lists of factors if it is in all the lists. A fraction remains equal if both its numerator above and denominator below are divided by a common factor. Those two divisions produce natural numbers because the division involves factors.

The list of common factors of 40 and 60 is {1,2,5,10,20}. The highest common factor is 20. Use it to divide both numerator 40 and denominator 60 of the first fraction to get the second fraction:
The reader can make the lists of all factors of 40 and of 60, and verify that the natural number 20 is the largest factor in both lists.

[2.19] (Highest Common Factor*) The highest common factor (or greatest common divisor) of two natural numbers is the largest factor that is in both lists of all factors.
Notation:   hcf(u,v) = highest common factor of natural numbers u and v.
Other notation:   gcd(u,v) is the greatest common divisor of natural numbers u and v.
Click here for a technical definition of hcf.

hcf(12,40) = 4.
From
    The list of all factors of 40 is   {1,2,4,5,8,20,40}
    The list of all factors of 48 is   {1,2,3,4,6,8,12,24,48}
it is seen that hcf(40,48) = 8.
The reader can verify:   hcf(8,10) = 2,   hcf(15,9) = 3,   hcf(12,12) = 12,   hcf(8,27) = 1.
Without the laborious work of finding and listing all factors, the following can be stated as true:   hcf(28459,28459) = 28459,   hcf(1,25943) = 1   hcf(10,20) = 10.
It is easy to expand [2.15] to define the hcf of more than two natural numbers: hcf(4,6,26) = 2. In this situation, there are three lists, a list of all factors of 4, a list of all factors of 6 and a list of all factors of 26. The numbers 1 and 2 are in all three lists, but nothing larger than 2 is in all three lists.

1 is a factor of every natural number. It may happen that it is the only number in both lists of all factors of two natural numbers, such as 8 and 27:     hcf(8,27) = 1.
   the list of all factors of 8 = {1,2,4,8};
   the list of all factors of 27 = {1,3,9,2 7}.

[2.20] (relatively prime*) Two natural numbers are relatively prime iff their greatest common factor is 1.

A fraction is (expressed) in lowest terms if its numerator and denominater are relatively prime.

The fraction 8/27 is expressed in lowest terms. The fraction 4/6 is not expressed in lowest terms because hcf(4,6) = 2. If the numerator 4 and the denominator 6 is divided by 2, then the equivalent fraction 2/3 is expressed in lowest terms. Division of numerator and denominator of a fraction by any common factor larger than 1 produces an equivalent fraction with smaller numerator and denominator.

For fraction u/v, if the numerator u and denominator v are both divided by hcf(u,v) the an equivalent fraction will be obtained that is expressed in lowest terms. This statement is based on the following.

[2.21] (Lemma) If both of any pair of natural numbers are divided by their highest common factor then the quotients are relatively prime natural numbers.

For example, hcf(15,25) = 5. 15/5 = 3, 25/5 = 5, and 3 and 5 are relatively prime. Another example, hcf(60,70) = 10. 60/10 =6, 70/10 = 7. 6 and 7 are relatively prime. Also,
The fractions are shown with their equivalent fractions that are in lowest terms.

Click here for a discussion supporting the lemma.

[2.22] (*) If a natural number k is a factor of two (unequal) natural numbers u and v, then k is a factor of their (absolute) difference |u - v|
In symbols:    if k | u and k | v    then     k   |   |u - v|.

For example, 3 is a factor of both 24 and 18. Therefore 3 is a factor of 24 - 18 = 6. (Choose the subtraction 24 - 18, and not 18 - 24.)   Since 7 is a factor of both 14 and 56 it is a factor of |14 - 56| = 42.

[2.23] (*) Two facts are critical for a first more efficient method for finding the hcf of two natural numbers:
  (a) The highest common factor of a natural number and itself is that natural number. hcf(u,u) = u.
  (b) The highest common factor of two different natural numbers is not changed if the larger number is replaced by their difference.
If u>v then hcf(u,v) = hcf(u-v,v);    if v>u then hcf(u,v) = hcf(u,v-u).

[2.24] (Subtraction algorithm for finding hcf*)
Given two natural numbers u,v. To find the hcf(u,v).
 (a): if u = v, then then u is the highest common factor. Exit algorithm.
 (b): if u and v are unequal,
    (b₁) if u>v then replace u by u-v: hcf(u,v) = hcf(u - v, v);
    (b₂) if v>u then replace v by u-v: hcf(u,v) = hcf(u,v - u ).

For example,
  hcf(40,60)
    = hcf(40,60-40)    (by b₂)
    = hcf(40,20)
    = hcf(40-20,20)    (by b₁)
    = hcf(20,20)
    = 20                    (by a).
Click here for another example of finding the hcf.

Click here for a computer program to execute the algorithm [2.20] and let the computer do the computation. But if the reader does the computation for hcf(1000,5) = 5 he will discover a type of inefficiency of [2.20]. Later another much more efficient alborithm will replace algorithm [2.20].

[2.25] (Transitive property of being a multiple*) If a first natural number is a multiple of a second natural number, and that second natural number is a multiple of a third natural number, then the first natural number is a multiple of the third.

The dual of "No factor of a natural number is greater than that natural number" is "No multiple of a natural number is less than that natural number." The duals of some true statements are false. One must be careful in forming dual statements of true statements. The dual of "each natural number has a finite number of factors" is "each natural number has an infinite number of multiples." A simple way to get all the multiples of any natural number is to multiple all the natural numbers by that number.

A multiple is common to two or more lists of multiples if it is in all the lists.
The list of all multiples of 4 is {4,8,12,16,20,24,28,32,36,40, ...}
The list of all multiples of 6 is {6,12,18,24,30,36,42, ...}
The list of all common multiples of 4 and 6 is {12,24,36,... }

[2.26] (Least Common Multiple*) The least common multiple of two natural numbers is the smallest multiple that is in both lists of all multiples.
Notation: lcm(u,v) = least common multiple of natural numbers u and v.
Click here for a technical definition of lcm.

Comparing the definition [2.26] of lcm with the definition [2.19] of hcf, it is obvious that the definitions are duals of each other.
lcm(4,6) = 12.

Recall the addition of fractions. To add two fractions it is necessary to have the same denominators. The numerator and denominator of each fraction can be multiplied by the same factor to make denominators equal. Therefore, the denominators must be a common multiple of the original denominators.
In the adjoining figure, 4 and 6 are the original denominators. Their product 24 is a common multiple. Multiply the numerator and denominator of the first fraction by 6 and multiply the numerator and denominator of the second fraction by 4 to get new fractions 18/24 and 4/24. These fractions are equavilent to the original 3/4 and 1/6, and can be added to get 22/24. Reduced to lowest terms the final fraction is 11/12.
In the second row of the figure the hcf(4,6) =12 is used as the common denominator. Less computation is needed there.

[2.27] (*) The product of the hcf and lcm of two natural numbers is equal to their simple product:

hcf(4,6) = 2;   lcm(4,6) = 12.     2 x 12   =   4 x 6.

There is no algorithm supplied here to find directly the lcm of two natural numbers u,v. The lcm(u,v) can be found by computing the hcf(u,v) and then evaluating the quotient in lcm(u,v) = uv/hcf(u,v). In short:    lcm = product/hcf . lcm (8,20) = 8 x 20/hcf(8,20) = 160/4 = 40. Since the hcf is a factor of both 8 and 20, it is possible to divide the hcf into the larger, namely 20 to get 5. lcm(8,20 = 8 x 20/hcf(8,20) = 8 x 20/4 = 8 x 5 = 40. This procedure may avoid some large numbers.

The proof of [2.27] uses the technical definitions of hcf and lcm and a repeat use of logical implication. Click here to see the proof. Another proof uses the complete factorization of any natural number (except 1) into powers of primes. Click here for a discussion of complete factorization. Click here to see a discussion supporting [2.27] using the complete factorization.

[2.28] (Lemma) If the product of two natural numbers is 1 then those natural numbers each equals 1. If uv = 1 then u = v = 1.

[2.29] (Lemma*) If two natural numbers are factors of each other, then those numbers are equal. If m | n   and   n | m    m = n.