mersenneforum.org > Math Basic Number Theory 3: gcd, lcm & Euclid's algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2016-10-07, 11:31 #1 Nick     Dec 2012 The Netherlands 3×13×43 Posts Basic Number Theory 3: gcd, lcm & Euclid's algorithm Let $$a$$ and $$b$$ be integers. An integer $$d$$ is called a common divisor or common factor 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 greatest common divisor, or highest common factor, of $$a$$ and $$b$$, written $$\gcd(a,b)$$ or hcf$$(a,b)$$. We call $$a$$ and $$b$$ coprime or relatively prime if $$\gcd(a,b)=1$$. Example 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. The Euclidean Algorithm (a simple 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 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. Example 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. Proposition 7 With any valid input values, the above version of the Euclidean Algorithm terminates and gives the correct output value. proof 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. The Euclidean Algorithm (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. Example 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. Let $$a$$ and $$b$$ be integers again. An integer $$m$$ is called a common multiple 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 least common multiple, or lowest common multiple, of $$a$$ and $$b$$, written lcm$$(a,b)$$. Example 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$$. Proposition 8 Let $$a$$ and $$b$$ be non-zero integers. Then $$a\mathbb{Z}\cap b\mathbb{Z}=m\mathbb{Z}$$, where $$m=lcm(a,b)$$. proof 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\}$$. Proposition 9 Let $$a$$ and $$b$$ be integers, not both 0. Then $$a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$$, where $$d=\gcd(a,b)$$. proof 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$$. ∎ Corollary 10 Let $$a$$ and $$b$$ be integers, not both 0. Then there exist integers $$m$$ and $$n$$ such that $$\gcd(a,b)=ma+nb$$. proof 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. Example 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. Proposition 11 Let $$a$$ and $$b$$ be integers, not both 0, and $$d=\gcd(a,b)$$. Then, for any integer $$c>0$$, $$\gcd(ca,cb)=cd$$. proof 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). ∎ Exercises 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). Last fiddled with by Nick on 2016-10-08 at 08:45 Reason: Fixed typo in exercise 17. And punctuation in example before proposition 9.
 2016-10-08, 01:11 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 100100111001112 Posts Signaling a small typo in the example before proposition 9, it is written "4.7" instead of "4, 7". Still reading it. Very nice job! Last fiddled with by LaurV on 2016-10-08 at 01:14
 2016-10-08, 02:02 #3 bgbeuning   Dec 2014 3×5×17 Posts 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.
2016-10-08, 02:50   #4
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by bgbeuning 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.
It's an artifact of the TeX rendering of the [$] tag. It's pretty annoying. 2016-10-08, 08:46 #5 Nick Dec 2012 The Netherlands 3×13×43 Posts Quote:  Originally Posted by LaurV Signaling a small typo in the example before proposition 9, it is written "4.7" instead of "4, 7". Thank you - I have fixed it. 2016-10-08, 09:05 #6 Nick Dec 2012 The Netherlands 3×13×43 Posts Quote:  Originally Posted by bgbeuning 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:  Originally Posted by CRGreathouse It's an artifact of the TeX rendering of the [$] tag. It's pretty annoying.
Let's resolve this issue together here:
http://www.mersenneforum.org/showthr...520#post444520

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2017-01-31 14:41 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 0 2016-12-03 11:42

All times are UTC. The time now is 01:56.

Fri May 14 01:56:55 UTC 2021 up 35 days, 20:37, 0 users, load averages: 3.33, 3.02, 2.90