A Computational Introduction to Number Theory

Basic properties of the integers:.........
1.1 Divisibility and primality
Consider the integers Z := {. . . ,−2,−1, 0, 1, 2, . . .}. For a, b ∈ Z, we say
that b divides a, or alternatively, that a is divisible by b, if there exists
c ∈ Z such that a = bc. If b divides a, then b is called a divisor of a, and
we write b | a. If b does not divide a, then we write b  a.
We first state some simple facts:
Theorem 1.1. For all a, b, c ∈ Z, we have
(i) a | a, 1 | a, and a | 0;
(ii) 0 | a if and only if a = 0;
(iii) a | b and a | c implies a | (b + c);
(iv) a | b implies a | −b;
(v) a | b and b | c implies a | c.
Proof. These properties can be easily derived from the definition using elementary
facts about the integers. For example, a | a because we can write
a = a · 1; 1 | a because we can write a = 1 · a; a | 0 because we can write
0 = a·0. We leave it as an easy exercise for the reader to verify the remaining
properties.

Another simple but useful fact is the following:
Theorem 1.2. For all a, b ∈ Z, we have a | b and b | a if and only if a = ±b.
Proof. Clearly, if a = ±b, then a | b and b | a. So let us assume that a | b and
b | a, and prove that a = ±b. If either of a or b are zero, then part (ii) of the
previous theorem implies that the other is zero. So assume that neither is
zero. Now, b | a implies a = bc for some c ∈ Z. Likewise, a | b implies b = ad
for some d ∈ Z. From this, we obtain b = ad = bcd, and canceling b from
both sides of the equation b = bcd, we obtain 1 = cd. The only possibility
is that either c = d = −1, in which case a = −b, or c = d = 1, in which case
a = b.

Any integer n is trivially divisible by ±1 and ±n. We say that an integer
p is prime if p > 1 and the only divisors of p are the trivial divisors ±1
and ±p. Conversely, an integer n is called composite if n > 1 and it is
not prime. So an integer n > 1 is composite if and only if n = ab for some
integers a, b with 1 < a < n and 1 < b < n. The first few primes are
2, 3, 5, 7, 11, 13, 17, . . . .
The number 1 is not considered to be either prime or composite. Also, we
do not consider the negative of a prime (e.g., −2) to be prime (although one
can, and some authors do so).
A basic fact is that any non-zero integer can be expressed as a signed
product of primes in an essentially unique way. More precisely:
Theorem 1.3 (Fundamental theorem of arithmetic). Every non-zero
integer n can be expressed as
n = ±pe1
1 · · · per
r ,
where the pi are distinct primes and the ei are positive integers. Moreover,
this expression is unique, up to a reordering of the primes.
Note that if n = ±1 in the above theorem, then r = 0, and the product
of zero terms is interpreted (as usual) as 1.
To prove this theorem, we may clearly assume that n is positive, since
otherwise, we may multiply n by −1 and reduce to the case where n is
positive.
The proof of the existence part of Theorem 1.3 is easy. This amounts
to showing that every positive integer n can be expressed as a product
(possibly empty) of primes. We may prove this by induction on n. If n = 1,
the statement is true, as n is the product of zero primes. Now let n > 1,
and assume that every positive integer smaller than n can be expressed as
a product of primes. If n is a prime, then the statement is true, as n is the
product of one prime; otherwise, n is composite, and so there exist a, b ∈ Z
with 1 < a < n, 1 < b < n, and n = ab; by the induction hypothesis, both a
and b can be expressed as a product of primes, and so the same holds for n.
The uniqueness part of Theorem 1.3 is by no means obvious, and most
of the rest of this section and the next section are devoted to developing a
proof of this. We give a quite leisurely proof, introducing a number of other
very important tools and concepts along the way that will be useful later.
An essential ingredient in this proof is the following:
Theorem 1.4 (Division with remainder property). For a, b ∈ Z with
b > 0, there exist unique q, r ∈ Z such that a = bq + r and 0 ≤ r < b.
Proof. Consider the set S of non-negative integers of the form a − zb with
z ∈ Z. This set is clearly non-empty, and so contains a minimum. Let r be
the smallest integer in this set, with r = a − qb for q ∈ Z. By definition,
we have r ≥ 0. Also, we must have r < b, since otherwise, we would have
0 ≤ r − b < r and r − b = a − (q + 1)b ∈ S, contradicting the minimality of
r.
That proves the existence of r and q. For uniqueness, suppose that a =
bq + r and a = bq + r, where 0 ≤ r < b and 0 ≤ r < b. Then subtracting
these two equations and rearranging terms, we obtain
r − r = b(q − q). (1.1)
Now observe that by assumption, the left-hand side of (1.1) is less than b in
absolute value. However, if q = q, then the right-hand side of (1.1) would
be at least b in absolute value; therefore, we must have q = q. But then by
(1.1), we must have r = r.

In the above theorem, it is easy to see that q = a/b, where for any real
number x, x denotes the greatest integer less than or equal to x. We shall
write r = a mod b; that is, a mod b denotes the remainder in dividing a by
b. It is clear that b | a if and only if a mod b = 0.
One can generalize the notation a mod b to all integers a and b, with b = 0:
we define a mod b := a − bq, where q = a/b.
In addition to the “floor” function ·, the “ceiling” function · is also
useful: for any real number x, x is defined as the smallest integer greater
than or equal to x.
Exercise 1.1. Let n be a composite integer. Show that there exists a prime
p dividing n, such that p ≤ |n|1/2.
Exercise 1.2. For integer n and real x, show that n ≤ x if and only if
n ≤ x.
Exercise 1.3. For real x and positive integer n, show that x/n = x/n.
In particular, for positive integers a, b, c, a/b/c = a/(bc).
Exercise 1.4. For real x, show that 2x ≤ 2x ≤ 2x + 1.
Exercise 1.5. For positive integers m and n, show that the number of
multiples of m among 1, 2, . . . , n is n/m. More generally, for integer m ≥ 1
and real x ≥ 0, show that the number of multiples of m in the interval [1, x]
is x/m.
Exercise 1.6. For integers a, b with b < 0, show that b < a mod b ≤ 0.
1.2 Ideals and greatest common divisors
To carry on with the proof of Theorem 1.3, we introduce the notion of an
ideal of Z, which is a non-empty set of integers that is closed under addition,
and under multiplication by an arbitrary integer. That is, a non-empty set
I ⊆ Z is an ideal if and only if for all a, b ∈ I and all z ∈ Z, we have
a + b ∈ I and az ∈ I.
Note that for an ideal I, if a ∈ I, then so is −a, since −a = a · (−1) ∈ I.
It is easy to see that any ideal must contain 0: since an ideal I must contain
some element a, and by the closure properties of ideals, we must have 0 =
a + (−a) ∈ I. It is clear that {0} and Z are ideals. Moreover, an ideal I is
equal to Z if and only if 1 ∈ I—to see this, note that 1 ∈ I implies that
for all z ∈ Z, z = 1 · z ∈ I, and hence I = Z; conversely, if I = Z, then in
particular, 1 ∈ I.
For a ∈ Z, define aZ := {az : z ∈ Z}; that is, aZ is the set of all integer
multiples of a. It is easy to see that aZ is an ideal: for az, az ∈ aZ and
z ∈ Z, we have az + az = a(z + z) ∈ aZ and (az)z = a(zz) ∈ aZ. The
set aZ is called the ideal generated by a, and any ideal of the form aZ
for some a ∈ Z is called a principal ideal.
We observe that for all a, b ∈ Z, we have a ∈ bZ if and only if b | a.
We also observe that for any ideal I, we have a ∈ I if and only if aZ ⊆ I.
Both of these observations are simple consequences of the definitions, as the
reader may verify. Combining these two observations, we see that aZ ⊆ bZ
if and only if b | a.
We can generalize the above method of constructing ideals. Fora1, . . . , ak ∈ Z, define
a1Z + · · · + akZ := {a1z1 + · · · + akzk : z1, . . . , zk ∈ Z}.
That is, a1Z + · · · + akZ consists of all linear combinations, with integer
coefficients, of a1, . . . , ak. We leave it to the reader to verify that a1Z+· · ·+
akZ is an ideal and contains a1, . . . , ak; it is called the ideal generated by
a1, . . . , ak. In fact, this ideal is the “smallest” ideal containing a1, . . . , ak, in
the sense that any other ideal that contains a1, . . . , ak must already contain
this ideal (verify).
Example 1.1. Let a := 3 and consider the ideal aZ. This consists of all
integer multiples of 3; that is, aZ = {. . . ,−9,−6,−3, 0, 3, 6, 9, . . .}.

Example 1.2. Let a1 := 3 and a2 := 5, and consider the ideal a1Z + a2Z.
This ideal contains 2a1 −a2 = 1. Since it contains 1, it contains all integers;
that is, a1Z + a2Z = Z.

Example 1.3. Let a1 := 4 and a2 := 6, and consider the ideal a1Z + a2Z.
This ideal contains a2 − a1 = 2, and therefore, it contains all even integers.
It does not contain any odd integers, since the sum of two even integers is
again even.

The following theorem says that all ideals of Z are principal.
Theorem 1.5. For any ideal I ⊆ Z, there exists a unique non-negative
integer d such that I = dZ.
Proof. We first prove the existence part of the theorem. If I = {0}, then
d = 0 does the job, so let us assume that I = {0}. Since I contains non-zero
integers, it must contain positive integers, since if z ∈ I then so is −z. Let
d be the smallest positive integer in I. We want to show that I = dZ.
We first show that I ⊆ dZ. To this end, let c be any element in I. It
suffices to show that d | c. Using the division with remainder property, write
c = qd + r, where 0 ≤ r < d. Then by the closure properties of ideals, one
sees that r = c − qd is also an element of I, and by the minimality of the
choice of d, we must have r = 0. Thus, d | c.
We next show that dZ ⊆ I. This follows immediately from the fact that
d ∈ I and the closure properties of ideals.
That proves the existence part of the theorem. As for uniqueness, note
that if dZ = dZ, we have d | d and d | d, from which it follows by
Theorem 1.2 that d = ±d.

For a, b ∈ Z, we call d ∈ Z a common divisor of a and b if d | a anda1, . . . , ak ∈ Z, define
a1Z + · · · + akZ := {a1z1 + · · · + akzk : z1, . . . , zk ∈ Z}.
That is, a1Z + · · · + akZ consists of all linear combinations, with integer
coefficients, of a1, . . . , ak. We leave it to the reader to verify that a1Z+· · ·+
akZ is an ideal and contains a1, . . . , ak; it is called the ideal generated by
a1, . . . , ak. In fact, this ideal is the “smallest” ideal containing a1, . . . , ak, in
the sense that any other ideal that contains a1, . . . , ak must already contain
this ideal (verify).
Example 1.1. Let a := 3 and consider the ideal aZ. This consists of all
integer multiples of 3; that is, aZ = {. . . ,−9,−6,−3, 0, 3, 6, 9, . . .}.

Example 1.2. Let a1 := 3 and a2 := 5, and consider the ideal a1Z + a2Z.
This ideal contains 2a1 −a2 = 1. Since it contains 1, it contains all integers;
that is, a1Z + a2Z = Z.

Example 1.3. Let a1 := 4 and a2 := 6, and consider the ideal a1Z + a2Z.
This ideal contains a2 − a1 = 2, and therefore, it contains all even integers.
It does not contain any odd integers, since the sum of two even integers is
again even.

The following theorem says that all ideals of Z are principal.
Theorem 1.5. For any ideal I ⊆ Z, there exists a unique non-negative
integer d such that I = dZ.
Proof. We first prove the existence part of the theorem. If I = {0}, then
d = 0 does the job, so let us assume that I = {0}. Since I contains non-zero
integers, it must contain positive integers, since if z ∈ I then so is −z. Let
d be the smallest positive integer in I. We want to show that I = dZ.
We first show that I ⊆ dZ. To this end, let c be any element in I. It
suffices to show that d | c. Using the division with remainder property, write
c = qd + r, where 0 ≤ r < d. Then by the closure properties of ideals, one
sees that r = c − qd is also an element of I, and by the minimality of the
choice of d, we must have r = 0. Thus, d | c.
We next show that dZ ⊆ I. This follows immediately from the fact that
d ∈ I and the closure properties of ideals.
That proves the existence part of the theorem. As for uniqueness, note
that if dZ = dZ, we have d | d and d | d, from which it follows by