A Computational Introduction to Number Theory and Algebra

Basic properties of the integers

1.1 Divisibility and primality

A central concept in number theory is divisibility.

Consider the integers Z = {. . . ,−2,−1, 0, 1, 2, . . .}. For a, b ∈ Z, we say that a divides b if az = b for some z ∈ Z. If a divides b, we write a | b, and we may say that a is a divisor of b, or that b is a multiple of a, or that b is divisible by a. If a does not divide b, then we write a – b.

We first state some simple facts about divisibility:

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 if and only if −a | b if and only if a | −b;

(iv) a | b and a | c implies a | (b + c);

(v) a | b and b | c implies a | c.

Proof. These properties can be easily derived from the definition of divisibility, using elementary algebraic properties of the integers. For example, a | a because we can write a · 1 = a; 1 | a because we can write 1 · a = a; a | 0 because we can write a ·0 = 0. We leave it as an easy exercise for the reader to verify the remaining properties. 2

We make a simple observation: if a | b and b 6= 0, then 1 ≤ |a| ≤ |b|. Indeed, if az = b 6= 0 for some integer z, then a 6= 0 and z 6= 0; it follows that |a| ≥ 1, |z| ≥ 1, and so |a| ≤ |a||z| = |b|.

Theorem 1.2. For all a, b ∈ Z, we have a | b and b | a if and only if a = ±b. In particular, for every a ∈ Z, we have a | 1 if and only if a = ±1.

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 the other must be zero as well. So assume that neither is zero. By the above observation, a | b implies |a| ≤ |b|, and b | a implies |b| ≤ |a|; thus, |a| = |b|, and so a = ±b. That proves the first statement. The second statement follows from the first by setting b := 1, and noting that 1 | a. 2

The product of any two non-zero integers is again non-zero. This implies the usual cancellation law: if a, b, and c are integers such that a 6= 0 and ab = ac, then we must have b = c; indeed, ab = ac implies a(b − c) = 0, and so a 6= 0 implies b − c = 0, and hence b = c.

Primes and composites. Let n be a positive integer. Trivially, 1 and n divide n. If n > 1 and no other positive integers besides 1 and n divide n, then we say n is prime. If n > 1 but n is not prime, then we say that n is composite. The number 1 is not considered to be either prime or composite. Evidently, n 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, . . . .

While it is possible to extend the definition of prime and composite to negative integers, we shall not do so in this text: whenever we speak of a prime or composite number, we mean a positive integer.