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

Nick · 2016-10-07, 11:31

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).

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".
Still reading it.
Very nice job!

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:

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.

Nick · 2016-10-08, 08:46

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.

Nick · 2016-10-08, 09:05

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

2016-10-07, 11:31	#1
Nick Dec 2012 The Netherlands 3462₈ 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 "name field" Jun 2011 Thailand 2·5,179 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

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

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.