mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Basic Number Theory 3: gcd, lcm & Euclid's algorithm (https://www.mersenneforum.org/showthread.php?t=21641)

 Nick 2016-10-07 11:31

Basic Number Theory 3: gcd, lcm & Euclid's algorithm

Let $$a$$ and $$b$$ be integers.
An integer $$d$$ is called a [B]common divisor[/B] or [B]common factor[/B] of $$a$$ and $$b$$ if $$d|a$$ and $$d|b$$.
Let $$S$$ be the set of all common divisors of $$a$$ and $$b$$. Then $$1$$ is an element of $$S$$, for example, (as is $$-1$$).
If $$a$$ and $$b$$ are both zero, then $$S$$ is the set $$\mathbb{Z}$$ of all integers and, in particular, $$S$$ has no maximum element.
If $$a>0$$ then no divisor of $$a$$ is greater than $$a$$ (by proposition 1) so no element of $$S$$ is greater than $$a$$, either.
And if $$a<0$$ then the divisors of $$a$$ are the same as those of $$-a$$, which is greater than zero, so in this case no element of $$S$$ exceeds $$-a$$.
The same holds for $$b$$ so it follows that, as long as $$a$$ and $$b$$ are not both zero, their set of common divisors has a maximum element.
We call this the [B]greatest common divisor[/B], or [B]highest common factor[/B], of $$a$$ and $$b$$, written $$\gcd(a,b)$$ or hcf$$(a,b)$$.
We call $$a$$ and $$b$$ [B]coprime[/B] or [B]relatively prime[/B] if $$\gcd(a,b)=1$$.

[U] Example[/U]
The divisors of 12 are $$\{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12\}$$
and the divisors of 30 are $$\{-30,-15,-10,-6,-5,-3,-2,-1,1,2,3,5,6,10,15,30\}$$,
so the set of common divisors of 12 and 30 is the intersection of the above two sets, which is $$\{-6,-3,-2,-1,1,2,3,6\}$$.
The maximum element in this set is 6, so $$\gcd(12,30)=6$$. Note that the other common divisors of 12 and 30 are not just less than 6 but also divide it.

This example illustrates the idea of the greatest common divisor, but not a particularly efficient way of calculating it.
As you probably know, an algorithm to do that was included in book 7 of Euclid's Elements (dating from around 300BC). Let us consider a simple version of it first.
For any integers $$a$$ and $$b$$ (not both 0), it follows from the definition of the greatest common divisor that $$\gcd(-a,b)=\gcd(a,b)$$ and $$\gcd(b,a)=\gcd(a,b)$$, so we may restrict our attention to the natural numbers and can ignore the order in which we give the 2 values.

[U] The Euclidean Algorithm[/U] (a simple version)
To find the greatest common divisor of 2 non-negative integers (not both 0).

[FONT=Fixedsys] [CODE]
While neither number is 0:
replace the larger number with their difference
(either way around if the numbers are equal).
At the end, one number is 0 and the other is the
greatest common divisor of the original numbers.
[/CODE][/FONT]

[U] Example[/U]
To find gcd(56,21):
[CODE]
56 21 Replace 56 with 56-21=35
35 21 Replace 35 with 35-21=14
14 21 Replace 21 with 21-14=7
14 7 Replace 14 with 14-7=7
7 7 Replace either number with 7-7=0
7 0 We have a 0 and the other number is 7, so gcd(56,21)=7.
[/CODE][U]Proposition 7[/U]
With any valid input values, the above version of the Euclidean Algorithm terminates and gives the correct output value.

[U]proof[/U]
Each step of the algorithm produces 2 non-negative integers whose sum is smaller than the sum of the values from the previous step. This cannot continue indefinitely, so the algorithm terminates.

Take any integers $$a$$ and $$b$$.
For any common divisor $$d$$ of $$a$$ and $$b$$, we have $$a\in d\mathbb{Z}$$ and $$b\in d\mathbb{Z}$$, and $$d\mathbb{Z}$$ is closed under subtraction (by proposition 3) so $$a-b\in d\mathbb{Z}$$ too, making $$d$$ a common divisor of $$a-b$$ and $$b$$.
Conversely, for any common divisor $$d$$ of $$a-b$$ and $$b$$, we have we have $$a-b\in d\mathbb{Z}$$ and $$b\in d\mathbb{Z}$$, and $$d\mathbb{Z}$$ is closed under addition (by exercise 4) so $$a=(a-b)+b\in d\mathbb{Z}$$ too, making $$d$$ a common divisor of $$a$$ and $$b$$.
Thus, for any integers $$a$$ and $$b$$, the common divisors of $$a-b$$ and $$b$$ are precisely the same as the common divisors of $$a$$ and $$b$$ and therefore, if $$b\neq 0$$ (so that the greatest common divisors are defined) it follows that $$\gcd(a-b,b)=\gcd(a,b)$$.
Conclusion: the 2 values produced at the end of each step of the algorithm have the same greatest common divisor as the starting values.
Moreover, for any integer $$a>0$$, the common divisors of $$a$$ and 0 are precisely the divisors of $$a$$ (since every integer divides 0), and the greatest divisor of $$a$$ is $$a$$ itself (by proposition 1), so $$\gcd(a,0)=a$$. Thus the output of the algorithm is the greatest common divisor of the 2 values produced in the last step, hence also that of the starting values. ∎

The above version of the algorithm is simple but often ends up subtracting the same number over and over again, so it is more efficient to use division with remainder instead of subtraction.

[U] The Euclidean Algorithm[/U] (standard version)
To find the greatest common divisor of 2 non-negative integers (not both 0).

[CODE]
While neither number is 0:
replace the larger number with the remainder on dividing it by the
smaller number (either way around if the numbers are equal).
At the end, one number is 0 and the other is the
greatest common divisor of the original numbers.
[/CODE][U]

Example
[/U]To find gcd(3267,126)

[CODE]
3267 126 3267=25x126+117 so replace 3267 with 117
117 126 126=1x117+9 so replace 126 with 9
117 9 117=13x9+0 so replace 117 with 0
0 9 We have a zero, and the other number is 9 so gcd(3267,126)=9.[/CODE]Let $$a$$ and $$b$$ be integers again.
An integer $$m$$ is called a [B]common multiple[/B] of $$a$$ and $$b$$ if $$a|m$$ and $$b|m$$.
Let $$S$$ be the set of all common multiples of $$a$$ and $$b$$. If $$a$$ or $$b$$ is zero then $$S=\{0\}$$ and $$S$$ has no positive elements.
If instead $$a$$ and $$b$$ are both non-zero, then $$S$$ has non-zero elements (the product $$ab$$ for example), and $$S$$ is symmetric so it has positive elements.
The minimum positive element of $$S$$ is called the [B]least common multiple[/B], or [B]lowest common multiple[/B], of $$a$$ and $$b$$, written lcm$$(a,b)$$.

[U] Example[/U]
The set of all multiples of 12 is the set $$12\mathbb{Z}=\{\ldots,-60,-48,-36,-24,-12,0,12,24,36,48,60,\ldots\}$$
while the set of all multiples of 30 is $$30\mathbb{Z}=\{\ldots,-120,-90,-60,-30,0,30,60,90,120,\ldots\}$$
so the set of common multiples of 12 and 30 is their intersection
$$12\mathbb{Z}\cap 30\mathbb{Z}=\{\ldots,-120,-60,0,60,120,\ldots\} =60\mathbb{Z}$$.
The minimum positive element in this set is 60, so lcm$$(12,30)=60$$.

[U]Proposition 8[/U]
Let $$a$$ and $$b$$ be non-zero integers.
Then $$a\mathbb{Z}\cap b\mathbb{Z}=m\mathbb{Z}$$, where $$m=lcm(a,b)$$.

[U]proof[/U]
Take any elements $$c,d\in a\mathbb{Z}\cap b\mathbb{Z}$$.
Then $$c$$ & $$d$$ are elements of $$a\mathbb{Z}$$ and, by proposition 3, $$a\mathbb{Z}$$ is closed under subtraction so $$c-d\in a\mathbb{Z}$$.
Similarly, $$c$$ & $$d$$ are elements of $$b\mathbb{Z}$$, which is closed under subtraction, so $$c-d\in b\mathbb{Z}$$ too, and therefore $$c-d\in a\mathbb{Z}\cap b\mathbb{Z}$$.
Thus the set $$a\mathbb{Z}\cap b\mathbb{Z}$$ is closed under subtraction as well, and it contains 0 so, by proposition 6, it follows that $$a\mathbb{Z}\cap b\mathbb{Z}=m\mathbb{Z}$$ for some unique integer $$m\geq 0$$.
As $$a$$ and $$b$$ are both non-zero, their product $$ab$$ is a non-zero element of $$a\mathbb{Z}\cap b\mathbb{Z}$$ and hence of $$m\mathbb{Z}$$, so $$m\neq 0$$. Thus $$m$$ is the smallest positive element of $$m\mathbb{Z}$$.
But $$m\mathbb{Z}=a\mathbb{Z}\cap b\mathbb{Z}$$, which is the set of all common multiples of $$a$$ and $$b$$, so its smallest positive element is (by definition) $$lcm(a,b)$$. Hence $$m=lcm(a,b)$$. ∎

We can do something similar for the greatest common divisor.

Let $$A$$ and $$B$$ be sets of numbers.
We define $$A+B=\{a+b:a\in A,b\in B\}$$
i.e. we write $$A+B$$ for the set of all numbers obtainable as the sum of a number in $$A$$ with a number in $$B$$.
For example, if $$A=\{2,5\}$$ and $$B=\{4,7\}$$ then $$A+B=\{2+4,2+7,5+4,5+7\}=\{6,9,12\}$$.

[U]Proposition 9[/U]
Let $$a$$ and $$b$$ be integers, not both 0.
Then $$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$, where $$d=\gcd(a,b)$$.

[U] proof[/U]
Take any elements $$m,n\in a\mathbb{Z}+b\mathbb{Z}$$.
Then $$m=r+s$$ for some $$r\in a\mathbb{Z}$$ and some $$s\in b\mathbb{Z}$$, and $$n=t+u$$ for some $$t\in a\mathbb{Z}$$ and some $$u\in b\mathbb{Z}$$.
By proposition 3, the sets $$a\mathbb{Z}$$ and $$b\mathbb{Z}$$ are each closed under subtraction, so $$r-t\in a\mathbb{Z}$$ and $$s-u\in b\mathbb{Z}$$, and therefore $$m-n=(r+s)-(t+u)=(r-t)+(s-u)\in a\mathbb{Z}+b\mathbb{Z}$$.
Thus $$a\mathbb{Z}+b\mathbb{Z}$$ is also closed under subtraction, and it contains 0+0=0 so, by proposition 6, $$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$ for some unique integer $$d\geq 0$$.
As $$a$$ and $$b$$ are not both 0, this set contains non-zero elements, so $$d>0$$.
Now $$a\in a\mathbb{Z}$$ so $$a=a+0\in a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$, and therefore $$d|a$$.
In the same way we have $$d|b$$ too, so $$d$$ is a common divisor of $$a$$ and $$b$$.
Take any integer $$d'$$ and suppose that $$d'$$ is also a common divisor of $$a$$ and $$b$$. Then $$a\in d'\mathbb{Z}$$ and $$d'\mathbb{Z}$$ is closed under subtraction so, by proposition 4, $$a\mathbb{Z}\subset d'\mathbb{Z}$$.
Similarly, $$b\in d'\mathbb{Z}$$ so $$b\mathbb{Z}\subset d'\mathbb{Z}$$.
And $$d'\mathbb{Z}$$ is closed under addition (exercise 4) so $$a\mathbb{Z}+b\mathbb{Z}\subset d'\mathbb{Z}$$.
But $$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$ so $$d\mathbb{Z}\subset d'\mathbb{Z}$$ hence $$d'|d$$ (exercise 6).
As $$d>0$$ it follows by proposition 1 that $$d'\leq d$$.
Thus $$d$$ is the greatest common divisor of $$a$$ and $$b$$. ∎

[U] Corollary 10[/U]
Let $$a$$ and $$b$$ be integers, not both 0.
Then there exist integers $$m$$ and $$n$$ such that $$\gcd(a,b)=ma+nb$$.

[U] proof[/U]
Let $$d=\gcd(a,b)$$. Then $$d\in d\mathbb{Z}=a\mathbb{Z}+b\mathbb{Z}$$ (by proposition 9) so $$d=ma+nb$$ for some $$m,n\in\mathbb{Z}$$. ∎

The integers $$m$$ and $$n$$ in the above corollary can be calculated using the extended version of the Euclidean Algorithm.

[U] Example
[/U]To find gcd(3267,126) and how to write it in the above form.
[CODE]Write 3267 as a multiple of 3267 plus a multiple of 126:
1) 1x3267-0x126=3267
Do the same for the other starting value, 126:
2) -0x3267+1x126=126
Dividing 3267 by 126 gives quotient 25 (and remainder 117)
so we subtract 25 times each term in equation 2 from the corresponding term
in equation 1:
3) 1x3267-25x126=117
Dividing 126 by 117 gives quotient 1 (and remainder 9)
so we subtract 1 times each term in equation 3 from the corresponding term
in equation 2:
4) -1x3267+26x126=9
Dividing 117 by 9 gives quotient 13 (and remainder 0)
so we subtract 13 times each term in equation 4 from the corresponding term
in equation 3:
5) 14x3267-363x126=0
Now that we have reached zero, the previous equation gives the greatest
common divisor and how to write it in the required form:
gcd(3267,126)=9=26x126-1x3267.[/CODE][U]

Proposition 11[/U]
Let $$a$$ and $$b$$ be integers, not both 0, and $$d=\gcd(a,b)$$.
Then, for any integer $$c>0$$, $$\gcd(ca,cb)=cd$$.

[U] proof[/U]
By proposition 9, $$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$ so $$\{am+bn:m,n\in\mathbb{Z}\}=\{dn:n\in\mathbb{Z}\}$$
and thus, for any integer $$c>0$$, $$\{cam+cbn:m,n\in\mathbb{Z}\}=\{cdn:n\in\mathbb{Z}\}$$
hence $$ca\mathbb{Z}+cb\mathbb{Z}=cd\mathbb{Z}$$.
So, by proposition 9 again, $$cd\mathbb{Z}=e\mathbb{Z}$$ where $$e=\gcd(ca,cb)$$.
Thus $$cd|e$$ and $$e|cd$$ (exercise 6), and $$cd$$ and $$e$$ are both positive (since $$c>0$$) so $$cd=e$$ (by proposition 2). ∎

[U]Exercises[/U]
11. Calculate $$\gcd(1159,793)$$ and find integers $$m$$ and $$n$$ such that $$\gcd(1159,793)=1159m+793n$$.
12. Show for any integers $$a$$ and $$b$$ not both 0 that the integers $$a/\gcd(a,b)$$ and $$b/\gcd(a,b)$$ are coprime.
13. Let $$A$$ be a set of numbers that is closed under addition with $$0\in A$$. Show that $$A+A=A$$.
14. Show that any two consecutive terms of the Fibonacci sequence are coprime.
15. Let $$a$$,$$b$$, and $$c$$ be integers with $$b\neq 0$$. Prove that $$\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))$$.
16. Find integers $$x$$,$$y$$ and $$z$$ such that $$45x+35y+42z=1$$.
17. Let $$a$$, $$b$$ and $$c$$ be positive integers with $$ab=c^2$$ and $$\gcd(a,b)=1$$. Show that $$a=d^2$$ for some integer $$d$$ (without using factorization into primes).

 LaurV 2016-10-08 01:11

Signaling a small typo in the example before proposition 9, it is written "4.7" instead of "4, 7".
Very nice job! :tu:

 bgbeuning 2016-10-08 02:02

Have not seen the bar symbol used as a suffix operator before.
Or is it a type setting thing.

For me the first line displays as

Let a(bar) and b(bar) be integers.

 CRGreathouse 2016-10-08 02:50

[QUOTE=bgbeuning;444509]Have not seen the bar symbol used as a suffix operator before.
Or is it a type setting thing.

For me the first line displays as

Let a(bar) and b(bar) be integers.[/QUOTE]

It's an artifact of the TeX rendering of the [[i][/i]$] tag. It's pretty annoying.  Nick 2016-10-08 08:46 [QUOTE=LaurV;444505]Signaling a small typo in the example before proposition 9, it is written "4.7" instead of "4, 7". [/QUOTE] Thank you - I have fixed it.  Nick 2016-10-08 09:05 [QUOTE=bgbeuning;444509]Have not seen the bar symbol used as a suffix operator before. Or is it a type setting thing. For me the first line displays as Let a(bar) and b(bar) be integers.[/QUOTE] [QUOTE=CRGreathouse;444511]It's an artifact of the TeX rendering of the [$] tag. It's pretty annoying.[/QUOTE]

Let's resolve this issue together here: