A number u is called a divisor of a number n if n = q.u for some number q. In other words the remainder n¬u = 0. We also say that n is divisible by u. We write the relation ‘n is divisible by a’ as n|≥a and the reverse relation ‘a is a divisor of n’ as a≤|n (the inadequate notation a|n is often used in the literature).
The relations of being a divisor and of being divisible by are reflexive order relations, that is they are: (1) reflexive: n≤|n. Proof: n = n.1 = 1.n. (2) antisymmetric: if n≤|m and m≤|n then m=n. Proof: m = n.h and n = m.k implies m = (m.k).h = m.(k.h) by associativity, and since m is not 0, k.h = 1, and so k = h = 1, hence in the original equations m=n. (3) transitive: if n≤|m and m≤|p then n≤|p. Proof: since m=n.h and p=m.k we have p = (n.h).k = n.(h.k) using associativity.
Divisors of a number are less than or equal to the number. In other words ≤| implies ≤. It follows that a nonzero number has only finitely many divisors. If a≤|n then a≤n. Proof: n = a.b for some b not 0, so b = 1 + (b−1), thus n = a.(1 + (b−1)) = a.1 + a.(b−1), using distributivity, thus n = a + c for some c, i.e. n ≥ a.
If n≤|m then n≤|(m.k), and (n.k)≤|(m.k) for any k.
If n≤|m and n≤|p then n≤|(m+p) and n≤|(mHp)
or more generally: n≤|(a.m + b.p), and n≤|(a.m H b.p)
for all nonzero a and b. Proof: m = h.n, p = q.n so a.m + b.p
= a.(h.n) + b.(q.n) = (a.h).n + (b.q).n
= (a.h + b.q).n, using associative and distributive properties.
Similarly for H.
If 0≤aHb≤n then n cannot be a divisor of both a and b.
For any numbers a and b (m not 0), a¬m = b¬m if and only if (aHb) is divisible by m.
The greatest common divisor of a set of numbers is the greatest number that is a divisor of all of them. We denote it by Λ(a,b,c,...), and we also write Λ(a,b) = aΛb.
Greatest Common Divisor (base ten)
| L | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | w | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 3 | 3 | 1 | 1 | 3 | 1 | 1 | 3 | 1 | 1 | 3 | 1 |
| 4 | 4 | 1 | 2 | 1 | 4 | 1 | 2 | 1 | 4 | 1 | 2 |
| 5 | 5 | 1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 1 | 5 |
| 6 | 6 | 1 | 2 | 3 | 2 | 1 | 6 | 1 | 2 | 3 | 2 |
| 7 | 7 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | 1 | 1 | 1 |
| 8 | 8 | 1 | 2 | 1 | 4 | 1 | 2 | 1 | 8 | 1 | 2 |
| 9 | 9 | 1 | 1 | 3 | 1 | 1 | 3 | 1 | 1 | 9 | 1 |
| 10 | 10 | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 10 |
Since every number divides 0 the GCD of (0,0,...) is the greatest number, u. The GCD can be evaluated for nonzero numbers by finding the prime divisors of all the numbers and taking the product of all the common prime factors to give the GCD. The GCD of a set including 0 and nonzero numbers is the same as for the set without 0.
The following is a list of properties of Λ:
Idempotency: aΛa = a.
Commutativity: aΛb = bΛa.
Associativity: (aΛb)Λc = aΛ(bΛc).
Lower bound: 1 ≤ aΛb.
Upper bound: aΛb ≤ min(a,b), except when a = 0 or b = 0.
Divisibility: aΛb = a if and only if a≤|b,
If r≤|a, r≤|b, ... then r≤|Λ{a,b, ...}.
Other properties:
Relation to addition: aΛb = (a+b)Λb.
Relation to symmetric difference: (a+b)Λ(aHb) > aΛb.
The Euclidean Algorithm: This is a method of calculating the GCD based on the fact that if two numbers have a common factor then the difference between them has the same factor. If a > b and a¬b = r(1), with b > r(1), then aΛb = bΛr(1). And if b¬r(1) = r(2), with r(1) > r(2), then bΛr(1) = r(1)Λr(2). Since each number in the sequence a, b, r(1), r(2), ... is progressively smaller we eventually arrive at a pair of numbers, r(k–1), r(k) such that r(k–1)¬r(k) = 0. We then have r(k–1)Λr(k) = r(k) = aΛb. The process always terminates.
Example (Reichmann): from 6600 and 2424 we get the series of remainders 1752, 672, 408, 264, 144, 120, 24, 0, so 6600Λ2424 = 24.
The least common multiple of a set of numbers, is the least number that is a multiple of all of them, we denote it V(a,b,c,...), and we also write V(a,b) = aVb.
Least Common Multiple (base ten)
| V | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 0 | 2 | 2 | 6 | 4 | 10 | 6 | 14 | 8 | 18 | 10 |
| 3 | 0 | 3 | 6 | 3 | 12 | 15 | 6 | 21 | 24 | 9 | 30 |
| 4 | 0 | 4 | 4 | 12 | 4 | 20 | 12 | 28 | 8 | 36 | 20 |
| 5 | 0 | 5 | 10 | 15 | 20 | 5 | 30 | 35 | 40 | 45 | 10 |
| 6 | 0 | 6 | 6 | 6 | 12 | 30 | 6 | 42 | 24 | 18 | 30 |
| 7 | 0 | 7 | 14 | 21 | 28 | 35 | 42 | 7 | 56 | 63 | 70 |
| 8 | 0 | 8 | 8 | 24 | 8 | 40 | 24 | 56 | 8 | 72 | 40 |
| 9 | 0 | 9 | 18 | 9 | 36 | 45 | 18 | 63 | 72 | 9 | 90 |
| 10 | 0 | 10 | 10 | 30 | 20 | 10 | 30 | 70 | 40 | 90 | 10 |
If the set includes 0 then the LCM is 0. The LCM of a set of nonzero numbers can be evaluated by finding the prime divisors of all the numbers and taking the product of these primes with their maximum multiplicities. For instance 24 = (2^3).3 and 90 = 2.(3^2).5 so 24V90 = (2^3).(3^2).5 = 360.
The LCM is closely related to the GCD since in all cases:
(aΛb).(aVb) = a.b.
The following properties of V are similar to those of Λ:
Idempotent: aVa = a.
Commutative: aVb = bVa.
Associative: aV(bVc) = (aVb)Vc.
Upper bound aVb ≤ a.b.
Lower bound: aVb ≥ max(a,b), except when a = 0 or b = 0, but not both.
Divisibility: aVb = a if and only if a|≥b.
If m|≥a, m|≥b, ... then m|≥V(a,b,...).
Other inter-relationships of LCM and GCD:
Cancellation condition: If aΛb = aΛc and aVb = aVc then b=c.
Distributivity of V over Λ: nV(mΛp) = (nVm)Λ(nVp).
Distributivity of Λ over V: nΛ(mVp) = (nΛm)V(nΛp).
A triplet relationship: Λ{aVb, bVc, cVa} = V{aΛb, bΛc, cΛa} [Baker].