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 :

- a | 0, 1 | a, a | a for any integer a
- if a | 1 then a = ±1
- 0 | a if an only if a = 0
- if a | b and b | c then a | c
- if a | b then ka | kb for any k
- if ka | kb and k ¹ 0, then a | b
- if a | b and a | c then a | bx + cy for any integers x, y
- if a | b and c | d then ac | bd
- 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:

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

The greatest common divisor has a number of simple properties:

- gcd(a, 0) = a
- gcd(a, 1) = 1
- 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 :

- gcd(ab, c) = 1 if and only if gcd(a, c) = gcd(b, c) = 1
- if a | c and b | c and gcd(a, b) = 1, then ab | c
- if a | bc and gcd(a, b) = 1 then a | c
- gcd(a,
b) = gcd(a
^{m}, b^{n}) 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_{1}
and r_{1} such that a = q_{1}b + r_{1} where 0 £ r_{1} < b. If r_{1} = 0,
then b | a and so gcd(a, b) = b, so we can suppose r_{1} ¹ 0. Then we can find q_{2} and r_{2}
such that b = q_{2}r_{1} + r_{2} where

0 £ r_{2} < r_{1}.
If r_{2} ¹ 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_{1}, r_{2}, … , 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_{1})
= … = 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_{1}.(bk) + r_{1}k

bk = q_{2}.(r_{1}k) + r_{2}k

…

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

This is simply the Euclidean Algorithm applied
to ak and bk, so gcd(ka, kb) = r_{n}k = 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:

- if a º b (mod n) and c º d (mod n) then a + c º b + d (mod n)
- if a º b (mod n) then a + c º b + c (mod n) and ac º bc (mod n)
- 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_{1}x º
b_{1} (mod n_{1}), a_{2}x º b_{2} (mod n_{2}), etc., which in turn
provides a list of simpler congruences of the form x º c_{1} (mod n_{1}), x º c_{2} (mod n_{2}), etc.

Lemma 1.13 (Chinese Remainder Theorem). Let n_{1},
n_{2}, … , 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_{1}
(mod n_{1}), x º a_{2}
(mod n_{2}), … , x º a_{r}
(mod n_{r}) has a simultaneous solution which is unique modulo n_{1}n_{2}
… n_{r}.

Proof : Let n = n_{1}n_{2} … n_{r}
and let N_{k} = n/n_{k}. Obviously, gcd(N_{k}, n_{k})
= 1. By Lemma 1.11, the congruence N_{k}x º 1 (mod n_{k}) has a unique solution x_{k}
modulo n_{k}. Let x' = a_{1}N_{1}x_{1} + a_{2}N_{2}x_{2}
+ … + a_{r}N_{r}x_{r}. Then x' º a_{k}N_{k}x_{k} (mod n_{k})
since n_{k} | N_{i} for i ¹
k. But since N_{k}x_{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.