Integers

Philip J. Erdelsky

December 12, 2002

Please e-mail comments, corrections and additions to the webmaster at pje@efgh.com.

1. Characterizing the Integers

The set Z⁺ of positive integers {1, 2, 3, ...} is simple and familiar, but describing it in a fully rigorous way is not trivial. Many of our theorems will seem to be so obvious that they shouldn't require proof.

As always in mathematics, we must start with some postulates. We try to choose a minimal set of the simplest and most obvious characteristics of the integers.

Some properties of the positive integers are easy to state. Each positive integer is followed by another positive integer, which is called its successor. The number 1 is the first positive integer, so it is not the successor of any other positive integer. Every other positive integer is the successor of one and only one positive integer.

The successor of n will be written as n+1. However, at this point we have not defined any other kind of addition.

We can define 2 rigorously as 1+1, 3 as 2+1, etc., continuing the sequence only as far as required for a particular discussion.

Another property is required, because there are number systems different from the positive integers that have all these properties. One such system consists of the positive integers, with the usual successor relation, and also two additional elements A and B, which are successors of each other.

The additional property is one that states, in effect, that every positive integer is 1, or 2, or 3, or 4, and so on indefinitely. Unfortunately, "and so on indefinitely" has no place in a rigorous definition, even though we may think we know what it means.

Fortunately, there is an alternative.

A subset of Z⁺ is said to be closed under successorship if it contains the successors of all its elements; that is, if n is in the subset, then n+1 is also in the subset. For example, {1, 2} is not closed under successorship, but {3, 4, 5, ...} is.

Now we can state the final required property of the positive integers: Any subset of Z⁺ which contains 1 and is closed under successorship contains all the positive integers.

Actually, we can make do with slightly weaker conditions, which are called the Peano Postulates:

Every positive integer has a successor.
The number 1 is not the successor of any positive integer.
Every positive integer other than 1 is the successor of at most one positive integer.
Any set of positive integers which contains 1 and is closed under successorship contains all the positive integers.

Two other fairly obvious properties of the positive integers can be proved as a theorem.

Theorem 1.1. Every positive integer other than 1 is the successor of exactly one positive integer, and no positive integer is its own successor.

Proof. Assume, for purpose of contradiction, that the positive integer n is different from 1 and is not the successor of any positive integer, or is its own successor. Then in either case the set Z⁺ - {n} violates Peano Postulate (4). █

Theorem 1.1 can also be stated in a more concise way. The successorship function f(n) = n+1 is a one-to-one mapping from Z⁺ onto Z⁺ - {1}.

It is now easy to show that 1, 2, 3 and 4 are all distinct. If 1 = 2, 1 = 3 or 1 = 4, then 1 would be the successor of 1, 2 or 3, respectively. If 2 = 3 or 3 = 4, then 2 or 3 would be its own successor. If 2 = 4 then 1 = 3 because each integer is the successor of only one integer, and 1 = 3 has already been excluded. Similar arguments can be used for any number of integers which can be listed and treated exhaustively.

We haven't defined subtraction yet, but for a positive integer n other than 1, we will use the notation n-1 to denote the integer whose successor is n.

2. Induction and Recursion

Peano Postulate (4) is often called the mathematical induction postulate, because it can be cast into that form.

The technique of mathematical induction has two steps. Take a statement about the integer n.

Step 1: Prove the statement for n = 1.
Step 2: Assume the statement is true for n and then prove it for n+1.

The statement must then be true for all positive integers. In Step 2, the assumption that the statement is true for n is often called the inductive hypothesis. The technique is given formal justification by the following theorem.

Theorem 2.1. Let S be a statement about a positive integer, and suppose that

S is true for 1,
for all n, if S is true for n then it is true for n+1.

Then S is true for all positive integers.

Proof. Let T be the set of all positive integers for which S is true. Then Peano Postulate (4) asserts that T contains all positive integers. █

In some cases we have to use double induction.

Theorem 2.2. Let S(m, n) be a statement about two positive integers, and suppose that

S(1, 1) is true,
for all m and n, S(m, n) implies S(m+1, n) and S(m, n+1).

Then S(m, n) is true for all pairs of positive integers.

Proof. Let T(n) be the statement "S(m, n) is true for all integers m ". Then we prove T(n) by induction.

For n = 1, T(1) becomes "S(m, 1) is true for all m ". This can be proved by induction on m:

For m = 1, S(m, 1) is true by hypothesis (1).
If S(m, 1) is true, then S(m+1, 1) is true by hypothesis (2).

Then we assume T(n), which becomes "S(m, n) is true for all m ". By hypothesis (2), "S(m, n+1) is true for all m ", which is T(n+1).

Hence T(n) is true for all n, which was the desired result. █

Closely related to mathematical induction is a technique called recursion. We can define a function f by defining f(1) and defining f(n+1) in terms of n and f(n). The following theorem shows that this technique does define a unique function on the positive integers.

Theorem 2.3. Let R be any nonempty set. Let F : R ⨯ Z⁺ ⟶ R and let A be any element of R. Then there is one, and only one function f : Z⁺ ⟶ R such that

f(1) = A
f(n+1) = F(f(n), n)

Proof. Consider all subsets S of Z⁺⨯ R that obey the following two conditions:

(1, A) ∈ S,
if (n, r) ∈ S then (n+1, F(r,n)) ∈ S.

Let T be the intersection of all such subsets. Then clearly T also obeys the same two conditions, and T is a proper subset of every other set that obeys the conditions.

Next, we prove by induction that for every positive integer n, there is one and only one r such that (n, r) is in T.

For n = 1 this amounts to the assertion that (1, A) is the only pair in T with first element 1. Assume, for purpose of contradiction, that (1, B) is in T for some B in R other than A. Then the set T - {(1, B)} obeys both conditions but T is not a proper subset of it.

Now suppose the hypothesis is true for n, and (n,r) is the sole pair in T with first element equal to n. Then (n+1, F(r,n)) is also in T. Assume, for purpose of contradiction, that (n+1, C) is in T for some C in R other than F(r,n). Then the set T - {(n+1, C)} obeys both conditions but T is not a proper subset of it.

For any positive integer n, let f(n) be the element of R such that (n, f(n)) belongs to T. Then it is easy to show that f is the required function.

It is easy to prove by induction that the function f is unique. █

There is essentially only one system of positive integers, as the following theorem shows.

Theorem 2.4. Any two systems obeying the Peano Postulates are isomorphic; i.e., if X and Y are two such systems, then there is a one-to-one correspondence f : X ⟶ Y such that f(1) = 1 and f(n+1) = f(n)+1.

Proof. By the previous theorem, there is a function f : X ⟶ Y such that

f(1) = 1

f(n+1) = f(n)+1

The function f is the required isomorphism, provided it is one-to-one and its range is all of Y.

We first show that f is one-to-one, i.e., that f(a) = f(b) implies that a = b. We use induction on the common value n of f(a) and f(b).

For n = 1, we have f(a) = f(b) = 1. If a is not equal to 1, then a = c+1 for some integer c, and hence f(a) = f(c+1) = f(c)+1, which is not equal to 1. Hence a = 1. Similarly, b = 1.

Now assume that f(a) = f(b) = n implies that a = b and consider f(c) = f(d) = n+1. Then c cannot be equal to 1, so c = g+1 for some integer g. Hence f(c) = f(g+1) = f(g)+1 = n+1, so f(g) = n. Similarly, d = h+1 and f(h) = n. By inductive hypothesis, g = h. Therefore c = g+1 = h+1 = d.

We now show that the range of f is all of Y. Clearly 1 is in the range, and if n is in the range, so is n+1. By mathematical induction, all elements of Y are in the range. █

3. Addition

The positive integers also have an addition operation. So far, we have seen only a single example of addition, n+1. We would like addition to be consistent with this example and obey the associative and commutative laws:

n+1 is the successor of n
m+(n+p) = (m+n)+p (addition is associative)
m+n = n+m (addition is commutative)

Theorem 3.1. There is exactly one way to define addition on Z⁺ such that addition is associative and n+1 is the successor of n for every positive integer n.

Proof. Let m be any positive integer. By Theorem 2.3 there is a function f_m such that:

f_m(1) = m+1,
f_m(n+1) = f_m(n)+1 for every positive integer n.

Then define m+n to be f_m(n). It is clear that for all positive integers m and n,

m+1 is the successor of m,
m+(n+1) = (m+n)+1 for every positive integer n.

We must now show that this operation is associative even when the last operand is not 1, i.e. that m+(n+p) = (m+n)+p for all positive integers m, n and p.

We use induction on p. For p=1 it has already been proven. Then if m+(n+p) = (m+n)+p,

m+(n+(p+1)) = m+((n+p)+1) = (m+(n+p))+1 = ((m+n)+p)+1 = (m+n)+(p+1),

so it is also true for p+1.

If ++ is another associative operation such that m++1 = m+1, then it can easily be shown by induction on m that m++n = m+n for every positive integer n. Hence the operation is unique. █

We didn't require addition to be commutative, but we can prove that it is.

Theorem 3.2. For any positive integers m and n, m+n = n+m.

Proof. We first prove the special case 1+n = n+1 by induction on n. For n=1 it is obvious. If 1+n = n+1, then 1+(n+1) = (1+n)+1 = (n+1)+1.

Now we prove the general case m+n = n+m by induction on m. For m=1 it reduces to the special case. If m+n = n+m then (m+1)+n = m+(1+n) = m+(n+1) = (m+n)+1 = (n+m)+1 = n+(m+1). █

We don't have subtraction yet, but we do have a cancellation law.

Theorem 3.3. If m+p = n+p for any positive integers m, n and p, then m = n.

Proof. We use induction on p. For p=1 the assertion is identical to Peano Postulate (3). If m+(p+1) = n+(p+1) then (m+p)+1 = (n+p)+1, so m+p = n+p by the same postulate, and m=n by the inductive hypothesis. █

The following theorems may seem obvious, but we'll need them in the next section.

Theorem 3.4. For any positive integers m and n, m+n is not equal to either m or n.

Proof. We use induction on n. For n=1, m+1 is not equal to 1 because 1 is not the successor of any positive integer. If m+n is not equal to n, then m+n+1 is not equal to n+1 because different integers cannot have the same successor.

Since addition is commutative, m+n is also not equal to m. █

Theorem 3.5. For any positive integers m and n, one and only one of the following holds:

(1) m = n.
(2) There is a positive integer p such that m+p = n.
(3) There is a positive integer q such that m = n+q.

Proof. Theorem 3.4 shows that (1) is incompatible with (2) or (3). Moreover, if (2) and (3) were both true, then m = m+p+q, which is impossible by Theorem 3.4. This shows that only one of the conditions can hold.

The other part is by double induction on m and n. If m=n=1 then (1) holds. Now assume that one of the conditions holds.

If m=n then m and n+1 obey (2) and m+1 and n obey (3).

If m+p = n, we consider two cases.

If p=1, then m+1 = n, so m+1 and n obey (1), and m and n+1 obey (2) because m+1+1 = n+1, so m+2 = n.

If p is not 1, then p = r+1 for some r, so m+r+1 = n. Then m+1 and n obey (2) and so do m and n+1.

The proof in the case where m = n+q is similar. █

4. Ordering

The order of the positive integers (1, 2, 3, etc.) is one of their most familiar properties, yet it is fairly difficult to examine rigorously.

Theorem 4.1 There is one and only linear ordering of the positive integers such that n < n+1 for every positive integer n, and m < n if, and only if, there is a positive integer p such that m+p = n.

Proof. Define m < n if there is a positive integer p such that m+p = n. If n < s then there is a positive integer t such that n + t = s. Then (m+p) + t = s, hence m + (p+t) = s and the relation is transitive. Theorem 3.5 shows that it is a linear order.

Let < be any linear order such that n < n+1 for any n. Then we show, by induction on p, that m < m+p for any positive integer p. For p=1 it is true by hypothesis. If m < m+p then m+p < m+p+1 by hypothesis, and m < m+p+1 because the operation is transitive. If m < n by the linear order, then by Theorem 3.5 m = n or there is a p or q such that m + p = n or m = n + q. The first possibility is eliminated because the operation is a linear order. The third possibility implies that n < m, this is also eliminated. Hence m + p = n. █

At this point, we can start to use some of the more obvious properties of the positive integers.

5. Counting

Two sets A and B have the same number of elements if there is a one-to-one correspondence between them, i.e. a function f : A ⟶ B such that f(x) = f(y) if and only if x = y. It is easily shown that this is an equivalence relation.

Let [1,n] represent the set of all positive integers less than or equal to n, i.e. {m ∈ Z⁺ | m ≤ n}. We say that this set has n elements. Any set that has the same number of elements as [1,n] also has n elements. Moreover, the criterion for this, a one-to-one correspondence between [1,n] and a set A, is a formal description of the everyday process of counting.

Theorem 5.1 The sets [1,m] and [1,n] have the same number of elements if and only if m = n.

Proof. If m=n, then [1,m] and [1,n] are identical. The converse can be proved by induction on m. If [1,1] and [1,n] have the same number of elements, any one-to-one correspondence between them must carry 1 into both 1 and n (and other elements of [1,n]). This is impossible unless n=1.

Now assume [1,m+1] and [1,n] have the same number of elements, and let f be a one-to-one correspondence between them. The previous argument shows that n=1 is not possible, so n-1 is a positive integer.

If f(m+1) = n, let g be f; otherwise define g by

g(m+1) = n,
g(f ^-1(n)) = f(m+1), and
g(p) = f(p), for all p not equal to m+1 or f ^-1(n).

Then g(m+1) = n, and g restricted to [1,m] is a one-to-one correspondence with [1,n-1]. By inductive hypothesis m = n-1, which is equivalent to m+1 = n. █

Theorem 5.2 If A and B are disjoint sets with m and n elements, respectively, then the union C of A and B has m+n elements.

Proof. Let f : A ⟶ [1,m] and g : B ⟶ [1,n] be one-to-one correspondences. Then define h : C ⟶ [1, m+n] in the obvious way:

h(x) = f(x) if x is in A,
h(x) = m + g(x) if x is in B.

The function h can be shown to be one-to-one. If x ≠ y then clearly h(x) ≠ h(y) if x and y are both in A or both in B. If x is in A and y is in B, then we can use the order properties established in the previous section to show that h(x) ≠ h(y).

Similarly, we can show that h is onto [1, m+n]. Let y be in [1, m+n]. Then consider the cases where y<m , y = m and y > m. If y < m or y = m, then h^-1(y) = f^-1(y). If y > m then y = m + p for some p, and h^-1(y) = g^-1(p). █

At this point, we can state a rather straightforward extension of mathematical induction.

Theorem 5.3 Let S be a statement about a positive integer, and suppose that

S is true for 1,
for all n, if S is true for [1,n] then it is true for n+1.

Then S is true for all positive integers.

Proof. Apply Theorem 2.1 for the statement "S is true for all integers between 1 and n, inclusive". █

This variant of mathematical induction is more convenient in many cases because the inductive hypothesis used to prove a statement S for n+1 is somewhat more general. It can be assumed that S holds for any or all of the integers between 1 and n, inclusive.

6. Multiplication

Multiplication of positive integers is another familiar operation. Informally, multiplication can be defined as repeated addition:

mn = m + m + m + ... + m (n times)

This suggests the following formal properties:

m1 = m
m(n+1) = mn + m

There is only one operation with these properties.

Theorem 6.1. There is exactly one way to define multiplication of positive integers such that m1 = m and m(n+1) = mn + m.

Proof. Let m be any positive integer. By Theorem 2.3 there is a unique function f_m such that:

f_m(1) = m
f_m(n+1) = f_m(n) + m for every positive integer n

We define mn = f_m(n). Then the desired properties follow directly from the definition of f. █

Multiplication has three properties that require proof.

Theorem 6.2. Multiplication of positive integers has the following properties:

m(n+p) = mn + mp (multiplication is distributive over addition)
m(np) = (mn)p (multiplication is associative)
mn = nm (multiplication is commutative)

Proof. We prove distributivity by induction on p. For p=1 distributivity follows from the way multiplication was defined. Now assume that m(n+p) = mn + mp. Then

m(n+(p+1)) = m((n+p)+1) = m(n+p) + m = (mn+mp)+m = mn+(mp+m) = mn+m(p+1).

We prove associativity by induction on p. For p=1 associativity is trivial. Now assume m(np) = (mn)p. Then

m(n(p+1)) = m(np + n) = m(np) + mn = (mn)p + mn = (mn)(p+1).

We prove commutativity in two steps. First, we prove by induction on m that 1m = m1 = m. For m=1 it is trivial. Now assume 1m = m. Then

1(m+1) = 1m + 1 = m+1.

Now we prove that mn = nm by induction on n. For n=1, this is the result just proven. Now assume mn = nm. Then

m(n+1) = mn + m = nm + m = m + nm = m(1+n) = m(n+1).

█

Since multiplication is commutative, distributivity works both ways:

m(n+p) = mn + mp,

(n+p)m = nm + pm.

One property of multiplication and ordering is easy to prove:

Theorem 6.3. If m, n, p and q are positive integers and m > n and p > q, then mp > nq.

Proof. By definition, there are positive integers u and v such that m = n+u and p = q+v. By the distributive and associative laws:

mp = (n+u)(q+v) = (n+u)q + (n+u)v = nq + uq + nv + uv = nq + (uq + nv + uv).

Hence mp > nq by definition. █

7. Zero

The concept of zero came rather late in the history of mathematics. The geometric methods of antiquity didn't require it.

Many properties of the positive integers are more easily described if we define an additional integer 0. The extended number system is called the set of nonnegative integers. The fundamental property of 0 is that it is an additive identity:

n + 0 = 0 + n = n where n is any nonnegative integer

It is easy to show that the addition of nonnegative integers is associative and commutative when addition of 0 is defined in this way. It can also be shown that 0 is the only additive identity; i.e., that m+n = n implies that m=0.

We want to define multiplication by 0 so the distributive law is still true:

mn = m(n+0) = mn + m0.

This is possible only if m0 = 0. If multiplication is to be commutative, 0m = 0, too.

It is easy to show that the associative, distributive and commutative laws hold for addition and multiplication of nonnegative integers when addition and multiplication by 0 are defined in these ways.

We extend the ordering relationship by defining 0 < n for every positive integer n. It is easy to show that the extended relationship is a linear order.

8. Negative Integers and Subtraction

We can expand the number system further by defining a negative integer (-n) corresponding to every positive integer n. We define addition of a positive integer and its and the corresponding negative integer as follows:

n + (-n) = (-n) + n = 0.

The positive integers, zero and the negative integers are together called the integers, and are usually represented by Z.

For completeness, we define (-0) to be 0; and if (-n) is a negative integer, then we define (-(-n)) to be n. Hence the above identity holds for every integer n. Also,

-(-n) = n

for every integer n, whether positive, negative or zero.

For every integer n, we define the absolute value |n| of n as follows:

if n is positive or zero, |n| = n,
if n is a negative integer, then |n| = (-n).

As we did with 0, we want to define other operations with negative numbers so the most of the properties of nonnegative integers will still hold.

The addition of a negative number and 0 must preserve the special status of 0 as the additive identity:

(-n) + 0 = 0 + (-n) = (-n).

When two negative numbers are added, we notice that, if the associative and commutative laws continue to hold, then

(-m) + (-n) + (m + n) = (-m) + m + (-n) + n = 0 + 0 = 0.

Hence we are required to define the addition of two negative numbers as follows:

(-m) + (-n) = (-(m+n)).

When a positive number m and negative number (-n) are added, there are three possibilities:

If m = n, then m + (-n) = m + (-m) = 0.
If m > n, then m = n + p for some positive p, and hence m + (-n) = n + p + (-n) = n + (-n) + p = 0 + p = p.
If m < n, then n = m + p for some positive p, and hence m + (-n) = m + (-(m+p)) = m + (-m) + (-p) = 0 + (-p) = (-p).

It can be shown that addition of integers, with these definitions for addition of negative integers, is still associative and commutative.

Surprisingly, extending the definition of multiplication to negative integers is easier.

If m and n are positive integers, then if the distributive law continues to hold for negative integers

m(-n) + mn = m((-n)+n) = m(0) = 0,

and we have to define

m(-n) = (-(mn)).

If multiplication is commutative, then

(-n)m = (-(nm)).

Similarly,

(-m)(-n) + (-m)n = (-m)((-n)+n) = (-m)0 = 0,

and we have to define

(-m)(-n) = (-((-m)n)) = mn.

It can be shows that the associative, commutative, and distributive laws hold when multiplication is defined in this way.

We previously proved that m < n if there is a positive integer p such that m + p = n. To maintain this property when m or n, or both, may be negative, we must define

m < n whenever m is negative and n is nonnegative
m < n whenever m and n are both negative and (-n) < (-m)

We are now in a position to define subtraction:

m - n = m + (-n).

If m and n are both positive, and m > n, then this agrees with the usual definition of subtraction. In this case m = n+p for some positive p, so m - n = n + p + (-n) = p + n + (-n) = p + 0 = p.

The use of negative numbers simplifies computations in many cases, even in applications where negative numbers do not appear in either the data or the results. For example, in a system without negative numbers an expression such as 5+6-7 can be evaluated as (5+6)-7 but not as 5+(6-7) because 6-7 would not exist.

9. Division

Integers can be added, subtracted or multiplied. Division is not always possible, unless we allow remainders. The following theorem is often called the division algorithm.

Theorem 9.1. If n (the dividend) is any integer and d (the divisor) is any positive integer, then there are unique integers q (the quotient) and r (the remainder) such that

n = qd + r and 0 ≤ r < d.

Proof. First we prove that q and r always exist.

If n=0 then q=r=0. If d=1 then q=n and r=0. If n=1 and d>1 then q=0 and r=1.

For n>1 and d>1, we use induction on n. By inductive hypothesis,

n = qd + r and 0 ≤ r < d.

Then clearly

n+1 = qd + r + 1.

If r+1 < d, this is the required result for n+1. Otherwise, r+1 = d. Then

n+1 = qd + r+1 = qd + d = (q+1)d,

which is the required result for n+1 with r=0.

If n < 0 then -n is positive, so

-n = qd + r and 0 ≤ r < d.

Hence

n = (-q)d - r

If r=0 this is the desired result. If r>0 then

n = (-q-1)d + d - r,

and d-r is in the required range.

Now assume that q' and r' are such that

n = q'd + r' and 0 ≤ r' < d.

Then

0 = (q-q')d + (r-r') and -d < r-r' < d.

Equivalently,

(q-q')d = r'-r and -d < r'-r < d.

But if q-q' ≥ 1 then (q-q')d ≥ d, and if q-q' ≤ -1 then (q-q')d ≤ -d. Hence q-q' = 0 and r'-r = 0. █

Although we can't always divide, we do have a cancellation law for multiplication:

Theorem 9.2. If m, n and d are integers, md = nd and d is not zero, then m=n.

Proof. If d is positive, then by the division algorithm there are unique integers q and r such that

md = nd = qd + r, 0 ≤ r < d,

We notice that q=m and r=0 or q=n and r=0 are two pairs that satisfy these conditions. Since the integers are unique, m=n. █

If d is nonzero and n = qd with remainder zero, then we say that

n is divisible by d, or
d divides n, or
d is a divisor of n, or
d|n

and q = n/d.

Some results about divisibility are obvious:

Any nonzero integer divides itself.
Any nonzero integer divides zero.
The only divisors of 1 are 1 and -1.
The integers 1 and -1 divide any integer.
If m divides n and n divides m, then m = n or m = -n.
If m divides n and n divides p, then m divides p.
If m and n are positive integers and m>n, then m does not divide n.
If m divides n and p, then m divides n+p and n-p.
If m divides n or p, then m divides np.

In our investigation of divisibility, we consider only positive integers; in most cases the extension to negative integers is trivial.

Let m and n be two positive integers. We say that g is the greatest common divisor of m and n if

g divides both m and n, and
every positive integer which divides both m and n also divides g.

The following theorem not only states that any two positive integers have a greatest common divisor, but also suggests a practical method of computing it. It is called the Euclidean algorithm.

Theorem 9.3. Any two positive integers m and n have a greatest common divisor g, and there are nonnegative integers a and b such that

am - bn = g.

Proof. Let z = m+n-1. We use induction on z. If z=1, then clearly m=n=1, g=1, a=1 and b=0.

If z > 1 no generality is lost by assuming that m ≤ n. (If m > n, we can use the same argument with m and n reversed.) By Theorem 9.1 there are integers q and r such that

n = qm + r, 0 ≤ r < m.

If r=0, then a=1, b=0 and g=m, and it is clear that g is the greatest common divisor of m and n.

If r is not zero, then we notice first that every divisor of m and n is also a divisor of r, and that every divisor of m and r is also a divisor of n. Hence the greatest common divisor of m and r is the same as the greatest common divisor of m and n.

Since m≤n, r<n and m+n-1 < m+r-1. Hence we can use the inductive hypothesis on m and r to obtain integers a', b' and g such that:

a'm - b'r = g.

Then it is easy to show that g and the following values of a and b satisfy all the requirements:

a = a' + b'q, b = b'.

█

The greatest common divisor of m and n is usually written (m,n) or gcd(m,n).

10. Prime Numbers

A prime number p is an integer greater than 1 which is not divisible any positive integer except 1 and p.

Theorem 10.1. Any integer greater than 1 is either prime or a product of primes.

Proof. We use induction. Clearly the statement is true for 1, albeit vacuously.

If an integer greater than 1 is prime, the statement is clearly true. If not, then it can be factored into two smaller integers, neither of which is 1. By inductive hypothesis, each of them is either prime or a product of primes. Hence the number itself is a product of primes. █

If gcd(m,n) = 1, then m and n are said to be relatively prime.

Theorem 10.2. If a prime p divides the product mn of two positive integers, then it divides either m or n (or both).

Proof. Assume, for purpose of contradiction, that p does not divide either m or n. Since p is prime, its only divisors are 1 and p. Since p does not divide m, the only common divisor of p and m must be 1. Then by Theorem 9.3, there are integers a and b such that

ap - bm = 1.

Similarly, there are integers c and d such that

cp - dn = 1.

Multiplying these two equations gives

acp² - adnp - cbmp + bdmn = 1.

Then every term on the left side is divisible by p, but the right member is not divisible by p. This is the desired contradiction. █

Corollary 10.3. If a prime divides the product of three or more positive integers, it must divide at least one of them.

Theorem 10.4. Let p₁ p₂ ... p_m = q₁ q₂ ... q_n, where all factors are prime. Then m=n and the right member contains the same factors as the left member, differing at most in order.

Proof. We use induction on m. If m=1, then n must also be 1, otherwise p₁ would be a product of primes and could not be prime itself. Hence p₁ = q₁.

If m>1, then by Corollary 10.3 p₁ must divide at least one of the factors in q₁ q₂ ... q_n. Since a prime cannot divide a different prime, p₁ must be equal to at least one of the factors in q₁ q₂ ... q_n.

We use Theorem 9.2 to strike this common prime from both sides. Then we use the inductive hypothesis on what remains. █

The following theorem follows directly from Theorems 10.1 and 10.4. It is called the Fundamental Theorem of Arithmetic.

Theorem 10.5. Every integer greater than 1 can be factored into one or more prime numbers in a way that is unique apart from the order of the factors.

10. Modular Arithmetic

Let M be a positive integer. Two integers m and n are said to be congruent with respect to the modulus M if the their difference m-n is divisible by N. Sometimes this is abbreviated to "congruent modulo M", or simply "congruent" when the modulus is understood. In symbols, the relationship is expressed as m ≡ n (mod M) or m ≡ n when the modulus is understood.

It is easily shown that congruence with respect to a particular modulus is an equivalence relationship:

It is reflexive: n ≡ n.
It is symmetric: m ≡ n implies that n ≡ m.
It is transitive: m ≡ n and n ≡ p imply that m ≡ p.

Congruence has other properties in common with equality. Congruent integers have congruent sums, differences and products; i.e., if a ≡ b and c ≡ d then a+c ≡ b+d, a-c ≡ b-d and ac ≡ bd. (However, a/c is not necessarily congruent to b/d, even if the quotients exist.)

We can then define addition and multiplication modulo M for the set {0, 1, 2, ..., M-1}. If m and n are in this set, then the modular sum and product of m and n are the remainders when m+n and mn, respectively, are divided by M. Modular arithmetic of this kind obeys the same commutative, associative and distributive laws as regular arithmetic. The ordering relationships do not apply, but zero retains its status as the additive identity and each integer n has a negative M-n. The symbol Z_M is used to represent the set {0, 1, 2, ..., M-1} with these operations.

Since congruence for a particular modulus is an equivalence relation, there are equivalence classes, which are often called the residue classes modulo M. The division algorithm shows that any integer is congruent to exactly one of 0, 1, 2, ..., M-1 modulo M; namely, the remainder when it is divided by M. This number is sometimes called its residue modulo M. The equivalence classes are sometimes used instead of the set {0, 1, 2, ..., M-1} as the numbers in modular arithmetic. However, this approach does not produce significantly different results.

If the modulus M is a prime number, we can also divide by any nonzero number. If n is in {1, 2, ..., M-1}, then the greatest common divisor of n and M is 1, and there are integers a and b such that an + bM = 1, so an ≡ 1, and amn ≡ m for any integer m. Hence the residue of am is m/n.

The following theorem is often called Fermat's Little Theorem (to distinguish it from the more famous Fermat's Last Theorem):

Theorem 10.1. Let p be a prime number, and let n be any integer. Then n^p ≡ n (mod p).

Proof. There are several proofs of this theorem. The most elementary one uses induction on n and the binomial theorem.

The theorem is obvious for n = 0 and n = 1.

For larger values of n, use the binomial theorem to write

(n + 1)^p = n^p + p n^p-1 + (p(p-1)/2!) n^p-2 + (p(p-1)(p-2)/3!) n^p-3 + ... + 1

Every binomial coefficient except the first and last is divisible by p. (This is where the fact that p is prime is used.) Hence (n + 1)^p ≡ n^p + 1. Moreover, n^p ≡ n by inductive hypothesis. Hence (n + 1)^p ≡ n+1.

This proves the theorem for all nonnegative n. For negative n when p ≠ 2, n^p = (-1)^p (-n)^p = (-1)(-n) = n.

In the special case where p = 2, the theorem asserts that n² and n are both even or both odd, which is fairly obvious. █

The theorem is sometimes stated in an equivalent form:

Corollary 10.2. Let p be a prime number, and let n be any integer not divisible by p. Then n^p-1 ≡ 1 (mod p).