[Math talk #26] Greatest Common Divisor

mathsolver (53)in #math • 6 years ago

The Greatest common divisor

In the last post I introduced the integer division algorithm. Given two integers $a, b$ with $b \neq 0$ , there exist unique quotient $q$ and remainder $r$ such that

$a = qb + r$ and
$0\leq r < |b|$

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

Divisors and multiples

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

$17 \mid 34$ because $34 = 17 \times 2$ , but $20 \nmid 34$ since $34 = 1 \times 20 + 14$ .
Any integer $a$ is a divisor of 0, since $a \times 0 = 0$ is always true.
Trivially, for any integer $a$ , $\pm 1$ and $\pm a$ are divisors of $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 $a, b$ . For example, let's just put $a = 36, b = 20$ . A natural question would be

What are the common divisors?

Divisors of $36$ are

$\pm1, \pm2, \pm3, \pm4, \pm6, \pm9, \pm 12, \pm18, \pm36$

and divisors of $20$ are

$\pm1, \pm2, \pm4, \pm5, \pm10, \pm 20$

It is clear that $\pm1, \pm2, \pm4$ 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 $a=b=0$ , then since every integer serves as a common divisor of $a, b$ , the set of positive divisors is infinite set, $\mathbb{N}$ . 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 $a, b$ is finite set. Finiteness guarantee the existence of greatest common divisor of $a$ and $b$ .

Greatest common divisor. Let $a, b$ be given integers, with at least one of them different from zero. Then greatest common divisor of $a$ and $b$ , denoted by $\gcd(a,b)$ , is the positive integer $d$ satisfying the following:

$d \mid a$ and $d \mid b$
If $c \mid a$ and $c \mid b$ , then $c \leq d$

Following the above example, the greatest common divisor is, $\gcd(36, 20) = 4$ .

Properties of greatest common divisor

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

Linear Diophantine Equation. Given integers $a, b$ , not both of which are zero, there exist integers $x, y$ such that

$\gcd(a,b) = ax + by$

For example, again using $a=36, b=20$ ,

$\gcd(36,20) = 4 = 36 \times (-1) + 20 \times 2$

so appropriate integers are $x=-1, y=2$ . 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 $ax + by$ .

$S = \left\{ ax + by : x, y \text{ are integers, } ax + by > 0\right\}$

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

$x=1, y=0$

$x=-1, y=0$

For special case of $a=0$ , we can use either $x=0, y=1$ or $x=0, y=-1$ . So, $S$ is clearly nonempty. Hence using the well ordering principle, there is a smallest element, namely $d$ . Again by definition of $S$ , there is a pair of integers $(x_0, y_0)$ such that

$d = ax_0 + by_0$

Now what's next? Well, we need to show that indeed $d = \gcd(a,b)$ ! This is straightforward.

If $d \nmid a$ , then the division algorithm gives a relation

$a = qd + r$

where $0 < r < d$ . However,

$r = a - qd=a(1-qx_0)+b(-qy_0)$
so that $r \in S$ . This contradicts to the fact that $d$ is the smallest element. Thus $d \mid a$ . The same argument applies to $b$ , so that $d \mid b$ .

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

Summing up, $d$ is greatest common divisor of $a$ and $b$ .

Only problem to this proof is that it does not explicitly show how to find pair $x_0, y_0$ . For example, if $a,b$ are large integers; say $a=1395, b=4890$ 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 $a$ and $b$ , not both of which are zero, are said to be relatively prime whenever $\gcd(a, b) = 1$ . Relatively prime integers are very special, because using linear diophantine theorem above, there is a pair of integers $x,y$ such that

$ax + by=1$

Therefore, the set $S$ is precisely, the set of positive integers, $\mathbb{N}$ .

Conclusion

$a$ is a divisor of $b$ if there exists another integer $c$ such that $b=ac$ .
Positive and negative divisors are symmetric, so positive divisors are enough.
The solution to linear diophantine equation $ax+by=c$ exists if and only if $c$ is a multiple of $\gcd(a,b)$ .
Relatively prime integers are the ones that $\gcd = 1$ .