[Math talk #26] Greatest Common Divisor
![](https://steemitimages.com/640x0/https://i.imgsafe.org/66/668fc101e8.jpeg)
(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,
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
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
- 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.
well post man, keep sharing...
You received 0.43 % upvote as a reward From round 3 on 2018.09.10. Congrats!
Quite phenomenal number theory studied hundreds of years ago would lead to today's cryptography.
Congratulations @mathsolver! You received a personal award!
You can view your badges on your Steem Board and compare to others on the Steem Ranking