## Integers## Philip J. Erdelsky## December 12, 2002 |

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

The set *Z ^{ +}* of positive integers

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

Now we can state the final required property of the positive integers:
Any subset of *Z ^{ +}* which contains

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

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

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, thenS(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.
█

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*for every positive integer_{m}(n+1) = f_{m}(n)+1*n*.

Then define *m+n* to be *f _{m}(n)*. It is clear that for
all positive integers

*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.
█

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.

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

**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*, and^{-1}(n)) = f(m+1)*g(p) = f(p)*, for all*p*not equal to*m+1*or*f*.^{-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

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.

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

mn = m + m + m + ... + m(ntimes)

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*for every positive integer_{m}(n+1) = f_{m}(n) + m*n*

We define *mn = f _{m}(n)*. Then the desired properties follow directly
from the definition of

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

We prove associativity by induction onm(n+(p+1)) = m((n+p)+1) = m(n+p) + m = (mn+mp)+m = mn+(mp+m) = mn+m(p+1).

We prove commutativity in two steps. First, we prove by induction onm(n(p+1)) = m(np + n) = m(np) + mn = (mn)p + mn = (mn)(p+1).

Now we prove that1(m+1) = 1m + 1 = m+1.

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

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.

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.

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 + rand0 ≤ 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 + rand0 ≤ 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'and0 ≤ r' < d.

Then

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

Equivalently,

(q-q')d = r'-rand-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 > (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)*.

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^{2}- 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 _{1} p_{2} ... p_{m} =
q_{1} q_{2} ... 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 _{1}* would be a product of primes and
could not be prime
itself. Hence

If *m>1*, then by Corollary 10.3 *p _{1}* must divide at least one of
the factors in

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

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

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,

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 ^{ 2}* and

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