Section 1 - Fundamentals

Whatever level of detail we start at, there must be a set of pre-suppositions. In our case, we shall take the basic arithmetic properties of integers and the associated operations of addition and multiplication, as understood. This includes the importance of 0 (zero) and 1 (one), in particular, that:

0 + n = n, 0*n = 0, 1*n = n, and that if ab = 0 then either a = 0 or b = 0.

We shall always use Z to represent the set if all integers, and N to represent the non-negative, or natural, integers, R for the real numbers and C for the complex numbers, though these last two don't appear until late on.

In addition, the following will be assumed :

The Well-Ordering Principle

The integers form a well-ordered set, that is, given any two integers a and b, then either a < b, a = b or a > b. This is obvious when the integers are defined from first principles using the successor operator. It is also obvious to our common sense view. In particular, for our uses, we can also presume the well-ordering principle, that any non-empty set of positive integers has a least member, which is obviously true by elimination.

The Induction Principle

If the integer 1 has a certain property, and whenever a positive integer k has this property, we can also show that the integer k+1 has this property, then all positive integers have this property. This can actually be proved using the well-ordering principle.

Subtraction and Division

Since we are dealing with all integers at the moment, subtraction is easily defined in the following way :

a - b = a + (- b) where (-b) is the additive inverse of b, i.e. x such that b + x = 0. We usually call a - b the difference between a and b.

As subtraction is the obvious counter-function to addition, so division fulfils this role for multiplication. We say that a divides b, written a | b, if we can find c such that b = ac. In this case, c also divides b. We may also say that b is divisible by a, or that a is a divisor, or factor of b. The number c is known as the cofactor when a is divided by b.

When a does not divide b, it is obvious that of all the multiples of a, i.e. 0, a, -a, 2a, -2a, … , etc. there must be one that is closest to b by the well-ordering principle applied to the set of positive integers |b-ma|, where m runs over all integers. This leads to the following important result.

Lemma 1.1 (The Division Algorithm). Given any two integers a and b, where b ¹ 0, there exist unique integers q and r such that a = qb + r where 0 £ r < |b|.

Proof : If a = 0 then we can take q = r = 0. Now suppose a ¹ 0. First, consider b > 0 and consider the set S of values a - xb for any integer x and such that a - xb ³ 0. This set is non-empty since we can take x = -|a|. By the well-ordering principle, S has a least member r = a - qb for some q. Suppose r ³ b. Then

a - (q + 1).b = (a - qb) - b = r - b ³ 0.

This implies that r - b is a member of S, which is impossible since r was chosen as the least member, and so we have r < b. To prove the uniqueness of q and r, suppose there are two representations, so that a = qb + r = q'b + r', and hence r' - r = (q - q')b. Since both r and r' are less than b, we know that 0 £ |r - r'| < b, and so |(q - q')| < 1. Since q and q' are integers, this can only happen if q = q', whence r = r'.

Now suppose b < 0. Then |b| > 0 and we can find q' and r such that a = q'|b| + r, where 0 £ r < |b|. Since |b| = - b, we can take q = - q' to get a = qb + r, as required.

We call q and r the quotient and remainder when a is divided by b. The special case r = 0 is synonymous with the statement that b divides a.

Division exhibits a number of straightforward properties, as follows:

Lemma 1.2 :

1. a | 0, 1 | a, a | a for any integer a
2. if a | 1 then a = ±1
3. 0 | a if an only if a = 0
4. if a | b and b | c then a | c
5. if a | b then ka | kb for any k
6. if ka | kb and k ¹ 0, then a | b
7. if a | b and a | c then a | bx + cy for any integers x, y
8. if a | b and c | d then ac | bd
9. if a | b then |a| £ |b|

Proof : straightforward and omitted.

Greatest Common Divisor

For any two integers a and b, consider the set S consisting of all positive common divisors d such that d | a and d | b, which is always non-empty since it always includes 1. The largest element of this set if called the greatest common divisor of a and b, written gcd(a, b).

Lemma 1.3. Given any two integers a and b, which are not both zero, there exist integers u and v such that gcd(a, b) = au + bv.

Proof : Let T be the set of combinations of the form ax + by for any integers x and y and such that ax + by > 0. This is non-empty since we can suppose that without loss of generality that a ¹ 0 and let y = 0 and x = 1 or - 1 depending on whether or not a is positive or negative. By the well-ordering principle, T has a smallest member d = au + bv. By the Division Algorithm, we can find q and r such that a = qd + r, where 0 £ r < d. Then r = a - qd = a - q.(au + bv) = a.(1 - qu) + b.(-qv). If r > 0 then this would mean that r is in T, contradicting the fact that d is the smallest member of T. Therefore r = 0 and so a = qd, i.e. d | a. Similarly, d | b, so d is a common divisor of a and b. If c is an arbitrary positive common divisor of a and b the c | ax + by for any x and y. In particular we have c | d and so c £ d, and so d = gcd(a, b).

From this proof we can extract several points:

1. If c | a and c | b and d = gcd(a, b), then c | d.
2. The set T is the set of positive multiples of d.

The greatest common divisor has a number of simple properties:

1. gcd(a, 0) = a
2. gcd(a, 1) = 1
3. gcd(a, b) = gcd(|a|, |b|)

Definition. Two integers a and b are relatively prime if gcd(a, b) = 1.

Lemma 1.4. If gcd(a, b) = d, then gcd(a/d, b/d) = 1.

Proof. Firstly, note that a/d = c where a = cd, since d | a. Since d = gcd(a, b), d = ax + by for some x and y. Dividing each side by d, we obtain 1 = (a/d)x + (b/d)y. We refer to Lemma 1.3 to deduce that a/d and b/d are relatively prime.

Note that the converse of Lemma 1.4 is trivially true.

There are various other simple relationships involving gcd and divisibility, as follows:

Lemma 1.5 :

1. gcd(ab, c) = 1 if and only if gcd(a, c) = gcd(b, c) = 1
2. if a | c and b | c and gcd(a, b) = 1, then ab | c
3. if a | bc and gcd(a, b) = 1 then a | c
4. gcd(a, b) = gcd(a^m, bⁿ) for all positive integers m and n

Proof of 1.5 (i) : Let d = gcd(a, c). Then d | a and d | c, and so d | ab and d | c. Hence gcd(ab, c) ³ d, so d = 1. An identical argument gives gcd(b, c) = 1. On the other hand, assume that gcd(ab, c) = d > 1. Then d has a prime divisor p. Since d | ab, we have p | ab, so either p | a or p | b. If p | a, then, since p | c by definition, we have gcd(a, c) ³ p, a contradiction. Supposing p | b leads to a similar contradiction. Hence d = 1 as required.

The Euclidean Algorithm

We will discover that removing common factors is an important step in dealing with primes numbers, and so it behoves us to be able to calculate the greatest common divisor efficiently. Listing all possible divisors and then selecting the largest is hardly useful in practice. However, a recursive process exists, based on the Division Algorithm, and works as follows:

Let a and b be two integers such that we wish to obtain gcd(a, b). Without loss, we will suppose that 0 £ b < a. Then we can find q₁ and r₁ such that a = q₁b + r₁ where 0 £ r₁ < b. If r₁ = 0, then b | a and so gcd(a, b) = b, so we can suppose r₁ ¹ 0. Then we can find q₂ and r₂ such that b = q₂r₁ + r₂ where
0 £ r₂ < r₁. If r₂ ¹ 0 we repeat the process until step n+1, say, where r_n+1 = 0, at which point we halt the algorithm. Since the sequence b, r₁, r₂, … , r_n is monotonically decreasing and bounded below by zero, it will always halt, again by the well-ordering principle.

Lemma 1.6. With the above definitions, gcd(a, b) = r_n.

For a proof of this, we need the following result.

Lemma 1.7. If a = qb + r, then gcd(a, b) = gcd(b, r).

Proof : Let d = gcd(a, b). Then since d | a and d | b, d | (a - qb), that is, d | r, and so d is a common divisor of b and r. If c is an arbitrary common divisor of b and r, then c | (qb + r), that is, c | a. Hence c is a common divisor of a and b, and so c | d. Hence d = gcd(b, r).

Proof of Lemma 1.6 : gcd(a, b) = gcd(b, r₁) = … = gcd(r_{n- 1}, r_n) = gcd(r_n, 0) = r_n as required.

A straightforward consequence of the Euclidean Algorithm is:

Lemma 1.8. For any integers k, a and b, gcd(ka, kb) = |k|.gcd(a, b).

Proof. First, suppose k > 0. We simply multiply each of the equations occurring in the Euclidean Algorithm by k, so that

ak = q₁.(bk) + r₁k

bk = q₂.(r₁k) + r₂k

…

r_{n- 1}k = q_{n- 1}.(r_nk) + 0

This is simply the Euclidean Algorithm applied to ak and bk, so gcd(ka, kb) = r_nk = k.gcd(a, b) as required. Now suppose k < 0. Then -k = |k| > 0 and so gcd(ka, kb) = gcd(-ka, -kb) = gcd(a.|k|, b.|k|) = |k|.gcd(a, b)

Congruences

Definition. Given integers a, b and c, a is congruence to b modulo c, written a º b (mod c), if the difference a - b is divisible by c. Congruence, although basically just an alternative and compressed notation for a simple idea, becomes a powerful tool to explore more complex issues involving the divisibility properties of integers, and the reader is highly encouraged to become completely familiar with its use.

If we look back to Lemma 1.1, and subtract r from both sides, we see that a º r (mod b), and so two integers a and a' are congruent modulo b if they have the same remainder when divided by b. We use the notation a (mod b) on its own as an alternative for the remainder, i.e. r = a (mod b) . In particular, a (mod b) < |b|. Another point to note is that for any positive integer n, every integer is congruent to one of the values 0, 1, 2, … , n-1 modulo n.

Congruence is an equivalence relation, i.e. it is reflexive, symmetric and transitive. Additionally, a lot of basic arithmetic can be translated, as follows:

1. if a º b (mod n) and c º d (mod n) then a + c º b + d (mod n)
2. if a º b (mod n) then a + c º b + c (mod n) and ac º bc (mod n)
3. if a º b (mod n) then a^k º b^k (mod n)

We now tie congruence in with greatest common divisor:

Lemma 1.9. For any a and n, if ax º ay (mod n) then x º y (mod n/d) where d = gcd(a, n).

Proof : By definition, ax - ay = a.(x - y) = kn for some k. Since d = gcd(a, n), we know that a = dr and n = ds for some r and s. Hence r.(x - y) = ks. Since gcd(r, s) = 1 (otherwise d would not be gcd(a, n)), we must have s | (x - y), that is, x º y (mod s), as required.

An immediate corollary of this is that if gcd(a, n) = 1, then the fact that ax º ay (mod n) implies that x º y (mod n).

Another useful result is the following:

Lemma 1.10. If a º b (mod n) then gcd(a, n) = gcd(b, n).

Proof : Let d = gcd(a, n). Then since d | a and n | a-b, we have d | a-b, hence d | b. Similarly, if e = gcd(b, n), then e | a. Since d | b and d | n, we have d | e, and since e | a and e | n, we have e | d, and so e = d.

Congruences can be used to investigate many divisibility properties of arbitrary numbers, for instance the fact that a number is divisible by 9 if and only if the sum of its digits is divisible by 9, using the following result.

Lemma 1.11. Let P(x) be a polynomial function of x with integral coefficients c_k for x^k. Then if a º b (mod n) then P(a) º P(b) (mod n).

Proof : Simply by combining various of the simple properties of congruence.

Linear Congruences

Definition. A linear congruence is an equation in one unknown of the form ax º b (mod n). Finding a solution of this is equivalent to finding a solution of the linear equation ax - ny = b.

Lemma 1.12. The linear congruence ax º b (mod n) has a solution if and only if d | b where d = gcd(a, n). Moreover, there are d mutually incongruent solutions modulo n.

Proof : The proof is straightforward but takes up too much space.

Given a linear congruence ax º b (mod n), the solution modulo n can be written as x º c (mod n). As with normal linear equations, we will often wish to find simultaneous solutions of systems of linear congruences a₁x º b₁ (mod n₁), a₂x º b₂ (mod n₂), etc., which in turn provides a list of simpler congruences of the form x º c₁ (mod n₁), x º c₂ (mod n₂), etc.

Lemma 1.13 (Chinese Remainder Theorem). Let n₁, n₂, … , n_r be positive integers such that gcd(n_i, n_j) = 1 for all i ¹ j. Then the system of linear congruences x º a₁ (mod n₁), x º a₂ (mod n₂), … , x º a_r (mod n_r) has a simultaneous solution which is unique modulo n₁n₂ … n_r.

Proof : Let n = n₁n₂ … n_r and let N_k = n/n_k. Obviously, gcd(N_k, n_k) = 1. By Lemma 1.11, the congruence N_kx º 1 (mod n_k) has a unique solution x_k modulo n_k. Let x' = a₁N₁x₁ + a₂N₂x₂ + … + a_rN_rx_r. Then x' º a_kN_kx_k (mod n_k) since n_k | N_i for i ¹ k. But since N_kx_k º 1 (mod n_k), we have x' º a_k (mod n_k) as required. For uniqueness, suppose another x'' satisfies the congruences. Then x'' º x' (mod n_k) for each k, and hence x'' º x' (mod n), as required.

We now have sufficient background knowledge to proceed to Section 2, in which primes are defined and some basic properties investigated.