(Image source Link, CC0 license)

The Greatest common divisor

In the last post I introduced the integer division algorithm. Given two integers with , there exist unique quotient and remainder such that

• and

Of special significance is the case in which the remainder turns out to be zero. ()

Divisors and multiples

We say an integer is divisible by if there exist another integer such that . Also is said to be divisor of . Conversely, is said to be multiple of . In mathematical notation, we write . For negation, we use the symbol to denote is not a divisor of . For example,

1. because , but since .

2. Any integer is a divisor of 0, since is always true.

3. Trivially, for any integer , and are divisors of . So any non zero integer has at least 4 divisors, two of which are postive and two of which are negative.

Commmon divisors

Suppose we are given two integers . For example, let's just put . A natural question would be

What are the common divisors?

Divisors of are

and divisors of are

It is clear that are common divisors. Exactly half of the common divisors are positive. Since negative divisors are nothing but negative sign attached to positive divisors, without loss of generality we can just consider about positive common divisors.

One more problem to resolve. If , then since every integer serves as a common divisor of , the set of positive divisors is infinite set, . So we must restrict our attention to pair of integers such that at least one is nonzero. Then, the set of positive common divisors of is finite set. Finiteness guarantee the existence of greatest common divisor of and .

Greatest common divisor. Let be given integers, with at least one of them different from zero. Then greatest common divisor of and , denoted by , is the positive integer satisfying the following:

• and

• If and , then

Following the above example, the greatest common divisor is, .

Properties of greatest common divisor

The most important property (or theorem) related with greatest common divisor is the following.

Linear Diophantine Equation. Given integers , not both of which are zero, there exist integers such that

For example, again using ,

so appropriate integers are . The existence, again, (if you read the previous post!) heavily relies on the well ordering principle. First, construct a collection of integers of the form .

We must show that is nonempty. Depending on the sign of , we can put

or

For special case of , we can use either or . So, is clearly nonempty. Hence using the well ordering principle, there is a smallest element, namely . Again by definition of , there is a pair of integers such that

Now what's next? Well, we need to show that indeed ! This is straightforward.

• If , then the division algorithm gives a relation

where . However,

so that . This contradicts to the fact that is the smallest element. Thus . The same argument applies to , so that .

• It is clear that the positive common divisors of a and b also divides .

Summing up, is greatest common divisor of and .

Only problem to this proof is that it does not explicitly show how to find pair . For example, if are large integers; say how do we find the pairs? Well, the actual construction will be the topic of next post, Euclidean algorithm.

Relatively prime integers

We say two integers and , not both of which are zero, are said to be relatively prime whenever . Relatively prime integers are very special, because using linear diophantine theorem above, there is a pair of integers such that

Therefore, the set is precisely, the set of positive integers, .

Conclusion

• is a divisor of if there exists another integer such that .

• Positive and negative divisors are symmetric, so positive divisors are enough.

• The solution to linear diophantine equation exists if and only if is a multiple of .

• Relatively prime integers are the ones that .

Next?

The Euclidean algorithm and Water bucket problem .

Notable sources

• Elementary number theory 7th edition by David M.Burton, Section 2-3.