Machì - Algebra for Symbolic Computation

Antonio Mach 1

(1)

Abstract

Let m be an arbitrary integer number (positive, negative or zero), n a positive integer, and let the set of multiples of n . There exist two consecutive terms of this sequence, qn and ( q + 1) n , such that:

Let m be an arbitrary integer number (positive, negative or zero), n a positive integer, and let the set of multiples of n . There exist two consecutive terms of this sequence, qn and ( q + 1) n , such that:

Let r be the difference

The operation consisting in finding the two numbers q and r is called division of m (dividend) by n (divisor). The integer q is the quotient (the greatest integer whose product by n is not greater than m , and as such it is uniquely determined), and r is the remainder of the division (which is uniquely determined as well). From (), by subtracting qn from each term, we get and hence: the remainder is never negative and is less than the divisor . If r = 0, the number m is said to be a multiple of n, and n is said to be a divisor of m, and we write n|m. If m 1 has no divisors but itself and 1, then m is a prime number.

Consider now two integers m and n , m n > 0, and look for the integers that divide both m and n. We shall see that the problem reduces to finding the divisors of a single integer d . Divide m by n:

It follows that r = m qn . It is then apparent that an integer dividing both m and n divides r too. On the other hand, if an integer divides n and r , the same equality tells us that that integer divides m too, so it divides both m and n . In other words, the common divisors of m and n coincide with those of n and r . Now, dividing n by r , we deduce as above that the common divisors of n ad r (hence those of m and n ) are those of r and of the remainder of the division. Going on this way, we get a sequence of divisions that eventually reach a remainder equal to zero, since the remainders are strictly decreasing non-negative integers (we have set q = q 1 and r = r 1): with the k th remainder r k equal to zero. By the above argument we have now that the common divisors of m and n are the common divisors of r k 1 (the last non-zero remainder) and 0 and, since all integers divide 0, we have that the common divisors of m and n are exactly the divisors of r k 1. Having set d = r k 1, we write d = (m, n) or d = gcd( m , n ). Now, d divides both m and n , and since among the divisors of d there is d itself, d is the greatest among the mutual divisors of m and n , hence the name of greatest common divisor of m and n . This name, however, conceals the main property of this number, lying not only in being the greatest among the divisors of both m and n , but in having as its divisors all the divisors of m and n .

So we have the following Euclidean algorithm :

If d = ( m , n ) = 1, then m and n have no common divisors different from 1: they are coprirne or relatively prime .

The remainder r 1 = m qn is a linear combination of m and n : and this holds for r 2 too: we have r 2 = n q 2 r 1 = n q 2 m + q 1 q 2 n; hence:

This happens for all the remainders r i , i = 1, , ..., k , so it also holds for r k- 1 = d . Hence, we have: