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,
because , but since .
Any integer is a divisor of 0, since is always true.
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.
