Rational Mathematics

by G. P. Jelliss

Divisibility

A number u is called a divisor of a number n if n = q.u for some number q. In other words the remainder nu = 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), am = bm if and only if (aHb) is divisible by m.

Greatest Common Divisor

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)
L012345678910
0w12345678910
111111111111
221212121212
331131131131
441214121412
551111511115
661232161232
771111117111
881214121812
991131131191
101012125212110

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 ab = r(1), with b > r(1), then aΛb = bΛr(1). And if br(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(k1), r(k) such that r(k1)r(k) = 0. We then have r(k1)Λ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.

Least Common Multiple

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)
V012345678910
000000000000
1012345678910
2022641061481810
30363121562124930
404412420122883620
50510152053035404510
606661230642241830
70714212835427566370
808824840245687240
9091893645186372990
10010103020103070409010

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].