A Notation for the GCD
and LCM Functions Abstract This paper proposes a notation to be used for the greatest common divisor (gcd) and least common multiple (lcm) functions in APL. The notation proposed is that in use for the logical or and and functions: ∨ for gcd and ^ for lcm. For this reason, special attention is paid to the cases of gcd and lcm for the arguments 0 and 1 . Also, because we wish to define the functions for negative and complex rational values as well as for positive integers, we discuss the functions more generally than is the case in standard number theory texts, which usually restrict their discussions to positive integers. For this reason we give proofs of some of the basic theorems concerning gcd and lcm, written to insure that they are valid for the entire domain of values for which it is proposed the APL functions be defined. The discussion in this paper is couched in terms of integral arguments. The theoretical extension to rational arguments is an easy one, and it is assumed that the gcd and lcm functions, which depend on the residue function for their definitions, will be implemented for nonintegral arguments, just as is the residue function, with all the practical difficulties which this entails. In this paper, the terms “greatest”
and “least” are taken to refer to magnitudes,
and the terms “divisor” and “multiple”
mean integer divisor and integer multiple.
0. Divisor and Multiple If m=d×h , where h is an integer, then m is a multiple of d , and d is a divisor of m . If d=0 , h is not uniquely defined, but nonetheless 0 is a divisor of 0 . A unit is a divisor of 1 .
There are two real units, ¯1
and 1 , and four complex units:
the two real units and the square
root of negative one and its negative.
Multiplication or division of a number by
a unit does not produce a change in its
magnitude, but will produce a change in
its direction, if the unit is not 1 .
Numbers which differ by unit multiples are associates.
Every number but zero has associates.
Every number is a divisor and multiple of itself
(from the identity n=n×1)
and associates are divisors and multiples of each other
(if a is associated with b ,
then a=b×u for some unit u).
Associates are equal in magnitude.
1. Zero as Divisor and Multiple From the identity 0=a×0
we conclude that
1) the only multiple of zero is zero;
2) zero is a divisor only of zero,
and no number but zero has zero as a divisor;
3) zero is the only number which is a
multiple of every number; and
4) there is no unique quotient for 0÷0 .
2. Common Divisors and Division Every number which is a divisor of each of two numbers is a common divisor of them. If d is a common divisor of h and k then the associates of d are also common divisors of h and k . If c=ab , then the common divisors of a and b are also common to c . For the definition of the residue function gives us c=ba×⌊b÷a . If e is any common divisor of a and b , then b÷e and (a×⌊b÷a)÷e are integers, as is their difference, to be called v . Thus we can write c=e×v , showing that e is also a divisor of c . The proof shows that the expressions c=a+b and c=ab may be substituted for c=ab in the statement of the theorem, and the theorem will remain true: that the common divisors of a and b are also common divisors of c . The common divisors of 0 and h are the divisors of h . This is easily seen using the algebra of sets. If i is the set of all numbers, these are the divisors of 0 . If d is the set of divisors of h , then d=i∩d . A proof for the division theorem valid for complex numbers in general is given in [6]. The theorem states that if z and w are arbitrary numbers, with w≠0 , then there exists an integer q , and an r such that z=r+q×w, and (r)<w . The proof depends on the definition of the complex floor function, which provides that 1>x⌊x for all x . q is determined by ⌊z÷w , and r by wz , and q and r are thus welldefined. If there is a nonempty set of integers
closed under addition and subtraction,
then the set is either zero alone or
consists of all multiples of some least
nonzero element.
In the first case,
where the set consists only of zero,
then 0+0 and 00
are in the set.
In the second case,
choose an element a≠0 .
Then 0 is in the set,
since 0=aa .
Now choose among the nonzero elements
least in magnitude
the element b .
Then all multiples of b
are in the set since it is closed under
addition and subtraction.
Conversely, all elements in the set
are multiples of b ,
since if a is
in the set, ba is also in the set,
since it is the difference of two
elements in the set; but ba
is less than b in magnitude
by the division theorem,
and so must be zero;
therefore a is a
multiple of b .
Clearly, the other least
elements are associates of b .
3. Greatest Common Divisor d is a greatest common divisor of h and k if it is a common divisor of h and k and is also a multiple of every other common divisor. It can be shown that every two integers h and k have a gcd d such that d=(p×h)+q×k , where p and q are integers, and d=0 if and only if h=0 and k=0 . In the first case, where h and k are not both zero, we see that for any two numbers of the form (p1×h)+q1×k and (p2×h)+q2×k , their sum ((p1+p2)×h)+(q1+q2)×k and difference ((p1p2)xh)+(q1q2)×k are also of that form. Therefore the set of all such linear combinations is closed under addition and subtraction, and thus contains 0 and a nonzero element d least in magnitude. d is a divisor of each element of the set. However h and k are both elements of the set (since h=(1×h)+0×k and k=(0×h)+1×k) and thus both have d as a divisor. For some integers p and q , d=(p×h)+q×k , and thus the common divisors of h and k are common divisors of d . Hence d is a greatest common divisor, for it is the greatest of the divisors of itself. If h and k are
both 0 ,
we know that every number is a common divisor
of 0 and 0 .
We know also that the only multiple of
every number is 0 .
Clearly, 0=(p×0)+q×0
for every p and q ,
and thus the gcd of 0 and 0
is 0 .
4. The Euclidean Algorithm For the purpose of defining a function, it is necessary to be able to specify one of the associated greatest common divisors as the greatest common divisor. This is accomplished by the Euclidean algorithm, as interpreted using the definition of the residue function current in APL. The residue function, in turn, is assumed to be using the definition of the complex floor function given in reference [6]. A version of the algorithm similar to one given in [4] is as follows: to compute the greatest common divisor of h and k , assign the values h and k to v , forming a twoelement vector. If the first element of v is zero, the algorithm terminates with the second element the result. If the first element of v is not zero, form a new first element by the process v←(/2↑v),v . This new element is thus the residue of the former second element, using the former first element as the modulus. The process will terminate if h and k are integers (real or complex), since the successive prefixed residues form a sequence of integers decreasing in magnitude, and thus the sequence is finite and ends in zero. The process will also terminate if h and k are rational (real or complex), but the argument is not as straightforward. When the algorithm described above terminates, the second element of v is the greatest common divisor of h and k . This is so because each overlapping pair of elements shares the same set of common divisors. Since v[1]=0 , the common divisors of v[1] and v[2] are the divisors of v[2] . So the divisors of v[2] are the common divisors of the elements of v , and in particular of the original elements of v , namely h and k . The greatest divisor of v[2] is of course v[2] , so the greatest common divisor of h and k (and of all the elements of v) is v[2] . One is not ordinarily interested in the intermediate values developed in the course of executing the algorithm. Iterative versions of the algorithm which do not maintain the intermediate residues are given in [3] and [4]. A recursively defined function is given below: d←h gcd k d←k →(0=h)/0 d←(hk) gcd h In a computer implementation of this
function for rationals on a system like
the IBM System 370, where nonterminating
decimals are approximated by finite
hexadecimals, the comparison 0=h
should be replaced by a comparison
of the magnitude of h
with some relatively small positive
number epsilon ,
in the form epsilon>h .
5. A Notation for the GCD Function The behavior of the gcd function with zero arguments has been discussed. It is evident that 0 is a leftright identity element for the function. If we tabulate the result of using all pairs of logical arguments with the function, we note that the gcd function is identical with the logical or function, denoted by ∨ : a b a gcd b 0 0 0 0 1 1 1 0 1 1 1 1 We adopt the ∨ notation forthwith to
denote the gcd function.
As is customary in APL,
the gcd of a vector of numbers v
may be found using reduction: ∨/v .
6. Least Common Multiple Every number which is a multiple of each of two numbers is a common multiple of them. If m is a common multiple of h and k , then the associates of m are also common multiples of h and k . Among the common multiples of two numbers, other than zero, one set of associates is less than any other set of associates. This set is called the least common multiples of h and k , and any member of this set is a least common multiple of h and k . Before investigating the lcm function, we must demonstrate several things. First we show that multiplication distributes over gcd, that is, ((m×h)∨m×k)=m×h∨k . If we multiply the vector v of the Euclidean algorithm (which contains a series of residues to the left of the original pair of arguments) by m , it is immediate that ((m×h)∨m×k)=m×h∨k . If 1=h∨k , then h and k are said to be relatively prime. Now we have to show that, if we let d←h∨k , and set h1←h÷d , and k1←k÷d , then h1 and k1 are relatively prime. The following listing gives four equal expressions: d h∨k (d×h1)∨d×k1 d×h1∨k1 and in particular the first and last expressions are equal, so that h1∨k1 must equal one, and therefore h1 and k1 are relatively prime. Now we are in a position to show that a least common multiple of two numbers h and k is given by (h×k)÷h∨k , and is 0 if and only if 0=h×k . In the first case, where h and k are not both zero, we make the following assignments: d←h∨k h1←h÷d k1←k÷d Any multiple of h has the form p×h and thus equals p×h1×d . For p×h to be divisible by k , the factor p×h1 must be divisible by k1 . Because 1=h1∨k1 , this is possible only when p is divisible by k1 , so that p=q×k1 . Any common multiple m of h and k is thus given by any of the equivalent forms: m p×h q×k1×h q×k1×h1×d q×h1×k1×d q×h1×k q×(h÷d)×k q×(h×k)÷d q×(h×k)÷h∨k It is clear that a least common multiple is obtained when q is equal to one. Therefore a least common multiple of h and k is given by (h×k)÷h∨k . The value so determined will be called the least common multiple. In the second case, when either h or k (but not both) is equal to zero, the result must be zero, since the only multiple of 0 is 0 . The formula (h×k)÷h∨k evaluates to 0 for both these cases. When h and k are both 0 , the formula becomes (0×0)÷0∨0 , or 0÷0 , an indeterminate form. Since the only multiple of 0 is 0 , this suggests that the value of 0÷0 in APL should be 0 (not 1 as is currently the case). For integral values n the function 1∨n
gives the result 1 .
Thus 1 is a left
identity for the lcm function,
that is, k=(1×k)÷1∨k
for all integer k .
It is not a right identity,
since any unit as a left
argument of lcm is a left identity element.
Thus (¯1×1)÷¯1∨1 evaluates
to ¯1÷¯1 or 1 .
7. A Notation for the LCM Function We have discussed the behavior of the lcm function with 0 arguments, and have seen that 1 is a left identity element. If we tabulate the results of all pairs of logical arguments, we note that the lcm function is identical to the logical and function, denoted by ^ : a b a lcm b 0 0 0 0 1 0 1 0 0 1 1 1 We adopt the ^ notation forthwith to
denote the lcm function.
As is customary in APL, the lcm of a vector
of numbers v may be found
using reduction: ^/v .
8. Some Properties of the GCD and LCM Functions For positive integer arguments, ∨ and ∧ are commutative and associative functions. For integers in general, or arbitrary rational arguments, neither of these is the case, as we saw with lcm and the arguments ¯1 and 1 . This arises from the fact that the residue function, which is central to both the gcd and the lcm function, is defined to be affected by the signum, or more generally, by the direction of the left argument. Thus (h)∨k and (h)∧k are different in general from h∨k and h∧k ; the difference lies in that the results of the two different forms will be associates. If we identify associates, then we can say that gcd and lcm are commutative and associative functions, for complex rational arguments in general. The gcd and lcm functions are replete with identities. A handful are given below.
The two columns of formulas are to be
understood to be connected with the
relation “is associated with”, in general,
and with the relation “is equal to”
if the arguments are restricted to positive
rationals and zero.
9. Conclusion The basic idea for the notation was
arrived at from a study of the properties
of the functions. Subsequently, it was
found that Greub, in
[2]
used essentially
the same notation for the gcd and lcm of
polynomials. Birkhoff and MacLane, in
[1],
use the same symbols, but interchanged.
The duality between the functions,
as evidenced by the identities given above,
permits this when the field
of discourse is restricted to the two functions.
Iverson, in
[5],
suggested the similarly shaped
symbols
and to denote
gcd and lcm, respectively.
The most common usage in number theory texts are
parentheses (h,k) for gcd
and brackets [h,k] for lcm.
These can not be employed
in a consistent system of notation because
of other conflicting uses of parentheses
and brackets and, more strongly, because
in APL we wish to denote a scalar dyadic
function by a single symbol infixed
between its arguments.
Extending the domain of the ∨ and ^
symbols accomplishes
this with no additions to the notation.
Acknowledgement Don Orth of the IBM Philadelphia
Scientific Center reviewed the manuscript
and made many helpful suggestions.
References
Bibliography
Note: The principal work consulted was
the paper by MacDuffee, which investigated
the properties of the gcd and lcm
functions for zero arguments. The texts
used for more conventional material were
Vinogradov (especially), Ore, and the
referenced work by Birkhoff and MacLane.
First appeared in the APL75 Conference Proceedings, 19750611 to 13. The sections in the original paper were not numbered.
