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 :
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:
The greatest common divisor has a number of simple properties:
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 :
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 q1
and r1 such that a = q1b + r1 where 0 £ r1 < b. If r1 = 0,
then b | a and so gcd(a, b) = b, so we can suppose r1 ¹ 0. Then we can find q2 and r2
such that b = q2r1 + r2 where
0 £ r2 < r1. If r2 ¹ 0 we repeat the process until step n+1, say, where rn+1 = 0, at which point we halt the algorithm. Since the sequence b, r1, r2, … , rn 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) = rn.
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, r1) = … = gcd(rn- 1, rn) = gcd(rn, 0) = rn 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 = q1.(bk) + r1k
bk = q2.(r1k) + r2k
rn- 1k = qn- 1.(rnk) + 0
This is simply the Euclidean Algorithm applied to ak and bk, so gcd(ka, kb) = rnk = 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)
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:
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 ck for xk. Then if a º b (mod n) then P(a) º P(b) (mod n).
Proof : Simply by combining various of the simple properties of congruence.
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 a1x º b1 (mod n1), a2x º b2 (mod n2), etc., which in turn provides a list of simpler congruences of the form x º c1 (mod n1), x º c2 (mod n2), etc.
Lemma 1.13 (Chinese Remainder Theorem). Let n1, n2, … , nr be positive integers such that gcd(ni, nj) = 1 for all i ¹ j. Then the system of linear congruences x º a1 (mod n1), x º a2 (mod n2), … , x º ar (mod nr) has a simultaneous solution which is unique modulo n1n2 … nr.
Proof : Let n = n1n2 … nr and let Nk = n/nk. Obviously, gcd(Nk, nk) = 1. By Lemma 1.11, the congruence Nkx º 1 (mod nk) has a unique solution xk modulo nk. Let x' = a1N1x1 + a2N2x2 + … + arNrxr. Then x' º akNkxk (mod nk) since nk | Ni for i ¹ k. But since Nkxk º 1 (mod nk), we have x' º ak (mod nk) as required. For uniqueness, suppose another x'' satisfies the congruences. Then x'' º x' (mod nk) 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.