<center> <img src = "https://i.imgsafe.org/66/668fc101e8.jpeg"/></center>
([Image source Link](https://pixabay.com/en/pay-digit-number-fill-count-mass-1036469/), CC0 license)
# The Greatest common divisor
In the [last post](https://steemit.com/math/@mathsolver/math-talk-24-integer-division-algorithm) I introduced the integer division algorithm. Given two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> with <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;\neq&space;0" title="b \neq 0" align = "center"/> , there exist unique quotient <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> and remainder <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> such that
- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;qb&space;+&space;r" title="a = qb + r" align = "center"/> and
- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0\leq&space;r&space;<&space;|b|" title="0\leq r < |b|" align = "center"/>
Of special significance is the case in which the remainder <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> turns out to be zero. (<img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r=0" title="r=0" />)
## Divisors and multiples
We say an integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" align = "center"/> is __divisible__ by <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> if there exist another integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> such that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;=&space;ac" title="b = ac" /> . Also <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="b" /> is said to be __divisor__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />. Conversely, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}b" title="a \mid b" align = "center"/> is said to be __multiple__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />. In mathematical notation, we write <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\mid&space;b" title="a \mid b" align ="center"/> . For negation, we use the symbol <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a\nmid b" title="\nmid" align = "center"/> to denote <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is __not__ a divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" align = "center" /> . For example,
1. <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;17&space;\mid&space;34" title="17 \mid 34" align = "center"/> because <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;34&space;=&space;17&space;\times&space;2" title="34 = 17 \times 2" align = "center"/>, but <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;20&space;\nmid&space;34" title="20 \nmid 34" align = "center"/> since <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;34&space;=&space;1&space;\times&space;20&space;+&space;14" title="34 = 1 \times 20 + 14" align = "center"/> .
2. Any integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is a divisor of 0, since <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\times&space;0&space;=&space;0" title="a \times 0 = 0" /> is always true.
3. Trivially, for any integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm&space;1" title="\pm 1" align ="center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm&space;a" title="\pm a" /> are divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />. 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 <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> . For example, let's just put <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;36,&space;b&space;=&space;20" title="a = 36, b = 20" align = "center"/> . A natural question would be
<center><b><i> What are the common divisors? </i></b> </center>
Divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;36" title="36" align = "center"/> are
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm3,&space;\pm4,&space;\pm6,&space;\pm9,&space;\pm&space;12,&space;\pm18,&space;\pm36" title="\pm1, \pm2, \pm3, \pm4, \pm6, \pm9, \pm 12, \pm18, \pm36" align = "center"/> </center>
and divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;20" title="20" /> are
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm4,&space;\pm5,&space;\pm10,&space;\pm&space;20" title="\pm1, \pm2, \pm4, \pm5, \pm10, \pm 20" /> </center>
It is clear that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm4" title="\pm1, \pm2, \pm4" align = "center"/> 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 <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=b=0" title="a=b=0" />, then since every integer serves as a common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align ="center"/>, the set of positive divisors is infinite set, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\mathbb{N}" title="\mathbb{N}" align = "center"/>. 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 <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> is __finite set__. Finiteness guarantee the existence of __greatest common divisor__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> .
---
___Greatest common divisor.___ Let <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> be given integers, with at least one of them different from zero. Then greatest common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, denoted by <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)" title="\gcd(a,b)" align = "center"/> , is the positive integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> satisfying the following:
- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;a" title="d \mid a" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;b" title="d \mid b" align ="center"/>
- If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\mid&space;a" title="c \mid a" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\mid&space;b" title="c \mid a" align = "center"/> , then <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\leq&space;d" title="c \leq d" align = "center"/>
---
Following the above example, the greatest common divisor is, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(36,&space;20)&space;=&space;4" title="\gcd(36, 20) = 4" align = "center"/> .
## Properties of greatest common divisor
The most important property (or theorem) related with greatest common divisor is the following.
---
___Linear Diophantine Equation.___ Given integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/>, not both of which are zero, there exist integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x,&space;y" title="x, y" align = "center"/> such that
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)&space;=&space;ax&space;+&space;by" title="\gcd(a,b) = ax + by" /> </center>
---
For example, again using <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=36,&space;b=20" title="a=36, b=20" align = "center"/>,
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(36,20)&space;=&space;4&space;=&space;36&space;\times&space;(-1)&space;+&space;20&space;\times&space;2" title="\gcd(36,20) = 4 = 36 \times (-1) + 20 \times 2" /> </center>
so appropriate integers are <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=-1,&space;y=2" title="x=-1, y=2" align = "center"/> . 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 <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax&space;+&space;by" title="ax + by" align = "center"/>.
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S&space;=&space;\left\{&space;ax&space;+&space;by&space;:&space;x,&space;y&space;\text{&space;are&space;integers,&space;}&space;ax&space;+&space;by&space;>&space;0\right\}" title="S = \left\{ ax + by : x, y \text{ are integers, } ax + by > 0\right\}" /> </center>
We must show that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is nonempty. Depending on the sign of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />, we can put
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=1,&space;y=0" title="x=1, y=0" /> </center>
or
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=-1,&space;y=0" title="x=-1, y=0" /> </center>
For special case of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=0" title="a=0" />, we can use either <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=0,&space;y=1" title="x=0, y=1" align = "center"/> or <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=0,&space;y=-1" title="x=0, y=1" align = 'center' />. So, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is clearly nonempty. Hence using the well ordering principle, there is a smallest element, namely <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> . Again by definition of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> , there is a pair of integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;(x_0,&space;y_0)" title="(x_0, y_0)" align = "center"/> such that
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;=&space;ax_0&space;+&space;by_0" title="d = ax_0 + by_0" /> </center>
Now what's next? Well, we need to show that indeed <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;=&space;\gcd(a,b)" title="d = \gcd(a,b)" align ="center"/> ! This is straightforward.
- If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\nmid&space;a" title="d \nmid a" align ="center"/> , then the division algorithm gives a relation
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;qd&space;+&space;r" title="a = qd + r" /> </center>
where <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0&space;<&space;r&space;<&space;d" title="0 < r < d" />. However,
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;=&space;a&space;-&space;qd=a(1-qx_0)+b(-qy_0)" title="r = a - qd=a(1-qx_0)+b(-qy_0)" /> </center>
so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;\in&space;S" title="r \in S" />. This contradicts to the fact that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> is the smallest element. Thus <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;a" title="d \mid a" align = "center"/> . The same argument applies to <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;b" title="d \mid b" align = 'center'/> .
- It is clear that the positive common divisors of a and b also divides <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> .
Summing up, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> is greatest common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> .
Only problem to this proof is that it does not explicitly show how to find pair <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x_0,&space;y_0" title="x_0, y_0" align = "center"/> . For example, if <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,b" title="a,b" align = "center"/> are large integers; say <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=1395,&space;b=4890" title="a=1395, b=4890" align ="center"/> 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 <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, not both of which are zero, are said to be __relatively prime__ whenever <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,&space;b)&space;=&space;1" title="\gcd(a, b) = 1" align = "center"/> . Relatively prime integers are very special, because using linear diophantine theorem above, there is a pair of integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x,y" title="x,y" align = "center"/> such that
<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax&space;+&space;by=1" title="ax + by=1" /> </center>
Therefore, the set <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is precisely, the set of positive integers, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\mathbb{N}" title="\mathbb{N}" /> .
## Conclusion
- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is a divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> if there exists another integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> such that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b=ac" title="b=ac" /> .
- Positive and negative divisors are symmetric, so positive divisors are enough.
- The solution to linear diophantine equation <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax+by=c" title="ax+by=c" align ="center"/> exists __if and only if__ <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> is a __multiple__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)" title="\gcd(a,b)" align = "center"/> .
- Relatively prime integers are the ones that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd&space;=&space;1" title="\gcd = 1" align = "center"/> .
## Next?
The Euclidean algorithm and Water bucket problem .
## Notable sources
- Elementary number theory 7th edition by David M.Burton, Section 2-3.
hiveblocks