mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-10-07, 11:31   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5AD16 Posts
Default 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.
Nick is offline   Reply With Quote
Old 2016-10-08, 01:11   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×3×739 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-10-08, 02:02   #3
bgbeuning
 
Dec 2014

22·32·7 Posts
Default

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.
bgbeuning is offline   Reply With Quote
Old 2016-10-08, 02:50   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·5·593 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2016-10-08, 08:46   #5
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,453 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Nick is offline   Reply With Quote
Old 2016-10-08, 09:05   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,453 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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 View Post
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
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Basic Number Theory 20: polynomials Nick Number Theory Discussion Group 5 2017-04-25 14:32
Basic Number Theory 17: quadratic reciprocity Nick Number Theory Discussion Group 0 2017-01-31 14:41
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42

All times are UTC. The time now is 19:54.

Sun Oct 25 19:54:57 UTC 2020 up 45 days, 17:05, 0 users, load averages: 1.58, 1.57, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.