20161007, 11:31  #1 
Dec 2012
The Netherlands
5AD_{16} 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 \(da\) and \(db\). 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 nonnegative 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 5621=35 35 21 Replace 35 with 3521=14 14 21 Replace 21 with 2114=7 14 7 Replace 14 with 147=7 7 7 Replace either number with 77=0 7 0 We have a 0 and the other number is 7, so gcd(56,21)=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 nonnegative 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 \(ab\in d\mathbb{Z}\) too, making \(d\) a common divisor of \(ab\) and \(b\). Conversely, for any common divisor \(d\) of \(ab\) and \(b\), we have we have \(ab\in d\mathbb{Z}\) and \(b\in d\mathbb{Z}\), and \(d\mathbb{Z}\) is closed under addition (by exercise 4) so \(a=(ab)+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 \(ab\) 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(ab,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 nonnegative 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. An integer \(m\) is called a common multiple of \(a\) and \(b\) if \(am\) and \(bm\). 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 nonzero, then \(S\) has nonzero 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 nonzero 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 \(cd\in a\mathbb{Z}\). Similarly, \(c\) & \(d\) are elements of \(b\mathbb{Z}\), which is closed under subtraction, so \(cd\in b\mathbb{Z}\) too, and therefore \(cd\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 nonzero, their product \(ab\) is a nonzero 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 \(rt\in a\mathbb{Z}\) and \(su\in b\mathbb{Z}\), and therefore \(mn=(r+s)(t+u)=(rt)+(su)\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 nonzero 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 \(da\). In the same way we have \(db\) 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) 1x32670x126=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) 1x326725x126=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) 14x3267363x126=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=26x1261x3267. 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 \(cde\) and \(ecd\) (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 20161008 at 08:45 Reason: Fixed typo in exercise 17. And punctuation in example before proposition 9. 
20161008, 01:11  #2 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×3×739 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 20161008 at 01:14 
20161008, 02:02  #3 
Dec 2014
2^{2}·3^{2}·7 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. 
20161008, 02:50  #4 
Aug 2006
2·5·593 Posts 

20161008, 08:46  #5 
Dec 2012
The Netherlands
1,453 Posts 

20161008, 09:05  #6  
Dec 2012
The Netherlands
1,453 Posts 
Quote:
Quote:
http://www.mersenneforum.org/showthr...520#post444520 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 1 & 2  Nick  Number Theory Discussion Group  17  20171223 20:10 
Basic Number Theory 20: polynomials  Nick  Number Theory Discussion Group  5  20170425 14:32 
Basic Number Theory 17: quadratic reciprocity  Nick  Number Theory Discussion Group  0  20170131 14:41 
Basic Number Theory 14: a first look at groups  Nick  Number Theory Discussion Group  0  20161229 13:47 
Basic Number Theory 11: Gaussian primes  Nick  Number Theory Discussion Group  0  20161203 11:42 