18 - The extended Euclidean algorithm

In class practice

An (integral) linear combination of two integers $a$ and $b$ is a number of the form $ax+by$ where $x,y\in \mathbb{Z}$.
$a=13,$ $b=3,$ $13(1)+3(-2)=7$

$n=qd+r$
$r=n-qd$

Theorem: Let $a$ and $b$ be integers, not both equal to $0$. The smallest positive integral linear combination of $a$ and $b$ is $GCD(a,b)$.

Outline of proof:
Let $s$ be the set of positive integral linear combinations of $a$ and $b$. Not both 0. Let $a,b\in \mathbb{Z}$. At least one is in $S$. By the theorem, $S$ has a least element. Call it $s$. By the division algorithm:

$0\le r\le s$.

$d=GCD(a,b)$.

Therefore $r\in S$ or $r=0$. Since $r<s$ and $s$ is the least element, $r\notin S$. Thus $r=0$.

=> a = qs
=> s | a
Similar s | b. So s is a common divisor $s\ge d$.

$d\mid a$ and $d\mid b$. Therefore, $d\mid ax+by$ for any $x,y\in \mathbb{Z}$.
Thus
$d\mid s$
$d\le s$
So $d=s$ since $s\le d$. Thus the GCD is the smallest positive integral linear combination of a and b.

GCD(512, 314)

E 18.9
GCD(221, 136) = 17
221 = 1(136) + 85
136 = 1(85) + 51
85 = 1(51) + 34
51 = 1(34) + 17
34 = 2(17) + 0

Remainders:
85 = 221 - 1(36)
51 = 136 - 1(85)
34 = 85 - 1(51)
17 = 51 - 1(34)

Let $a,b\in \mathbb{Z}$. GCD(a, b) = 1 iff $ax+by=1$ for some $x,y$.

Def $GCD(a,b)=1$, we say $a$ and $b$ are relatively prime.

Theorem. Let $a,b,c\in \mathbb{Z}$. If $a\mid bc$ and $GCD(a,b)=1$ then $a\mid c$. If $a\mid C$ and $b\mid c$ and $GCD(a,b)=1$ then $ab\mid c$.

HW 18

E 18.1
a) GCD(15, 27)
27 = 1(15) + 12
15 = 1(12) + 3
12 = 4(3) + 0
GCD = 3

Remainders:
12 = 27 - 1(15)
3 = 15 - 1(12)

Linear Combination of GCD

b) GCD(29, 23)
29 = 1(23) + 6
23 = 3(6) + 5
6 = 1(5) + 1
5 = 5(1) + 0
GCD = 1

Remainders
6 = 29 - 1(23)
5 = 23 - 3(6)
1 = 6 - 1(5)

Linear combination of the GCD

c) GCD(91, 133)
133 = 1(91) + 42
91 = 2(42) + 7
42 = 6(7) + 0
GCD = 7

Remainders:
42 = 133 - 1(91)
7 = 91 - 2(42)

Linear combination:

d)
GCD(221, 377)
377 = 1(221) + 156
221 = 1(156) + 65
156 = 2(65) + 26
65 = 2(26) + 13
26 = 2(13) + 0
GCD = 13

Remainders:
156 = 377 - 1(221)
65 = 221 - 1(156)
26 = 156 - 2(65)
13 = 65 - 2(26)

Linear combination:

E 18.2
Proof.

Let $a,n\in \mathbb{Z}$. Assume that $GCD(a,n)=1$. We aim to prove that there is some $b$ such that $ab\equiv 1$ (mod $n$) or in other words $ab-1=nk$ for some $b,k\in \mathbb{Z}$. By theorem 18.10, we see that $1=ab+nk$ since $GCD(a,n)=1$. Solving for $nk$ yields $ab-1=nk$ which satisfies the definition of modulus. Thus $ab\equiv 1\text{ (mod) }n$. $◻$

E 18.3
a)
Proof.
Let $a,b\in \mathbb{Z}$, $b\ne 0$. Let $d=GCD(a,b)$.
We aim to prove $GCD(a,\frac{b}{d})=1$.

Since $d$ is the greatest common divisor of $a$ and $b$, we can write $a=dm$ and $b=dn$, where $m$ and $n$ are integers. Since $d$ divides $a$ and $b$, it also divides any linear combination of $a$ and $b$. Therefore, we have:

Now, we show that $GCD(a,n)=1$. Suppose there exists a common divisor $c$ of $a$ and $n$ such that $c>1$. Then, $c$ divides both $a$ and $n$, so it must also divide $b$. However, this contradicts the fact that $d=GCD(a,b)$. Therefore, $GCD(a,n)=1$, which completes the proof. $◻$

b)
Let $a,b\in \mathbb{Z}$, $b\ne 0$. Let $d=GCD(a,b)$. We work directly. Assume $c$ is a positive common divisor of $a$ and $b$, and $c=ax+by$. We aim to prove $c=d$

$c\le d$ since $c$ is also a common divisor of $a$ and $b$ but possibly not larger than $d$.

Per our assumption, given that $c$ is a common divisor of $a$ and $b$ and $c=ax+by$, $c\ge d$ per Theorem 18.5.

Since we have $c\le d$ and $d\le c$, it follows that $c=d$. $◻$

E 18.4
Let $a,b,n\in \mathbb{Z}$, and fix $d=GCD(a,b)$. We aim to prove that $d\mid n$ iff $n$ is a linear combination of $a$ and $b$.

($=>$) We work directly. Assume $d\mid n$. Thus $n=dk$ for some $k\in \mathbb{Z}$. Since $d=GCD(a,b)$, per Theorem 18.5, $d=ax+by$ for some $x,y\in \mathbb{Z}$. We find

Thus $n$ is a linear combination of $a$ and $b$.
(<=) We work directly. Assume $n$ is a linear combination of $a$ and $b$. Then $n=ax+by$ for some $x,y$ in $\mathbb{Z}$.

Because $d$ is the greatest common divisor of $a$ and $b$, we can say $a=de$ and $b=df$ for some $e,f\in \mathbb{Z}$.

Substituting $a$ and $b$ into our expression for $n$ gives:

This demonstrates that $d$ divides $n$, as $ex+fy$ is an integer.

Therefore, we have proven that $d\mid n$ if and only if $n$ is a linear combination of $a$ and $b$. $◻$

E 18.5
Proof.
Let $a,b,n\in \mathbb{Z}$. Assume that $GCD(a,b)=1$. We aim to prove that if $c\mid a$ and $d\mid b$ then GCD($c,d$) = 1. We work directly. Since $GCD(a,b)=1$, $1=ax+by$ for some $x,y\in \mathbb{Z}$. Assume that $c|a$ and $d|b$. Thus $a=mc$ and $b=nd$ for some $m,n\in \mathbb{Z}$. We find

Since $(mx)$ and $(ny)$ are integers, c and d are linear combinations of 1. Per Theorem 18.5, if we can write 1 as a linear combination of c and d, GCD(c, d) = 1 since 1 is the smallest possible positive integer linear combination of two integers. $◻$

E 18.6
a) Let $a,b\in \mathbb{Z}$, not both zero. Let $d=GCD(a,b)$. We want to show that $GCD(\frac{a}{d},\frac{b}{d})=1$. Since $d$ divides both $a$ and $b$, $\frac{a}{d}$ and $\frac{b}{d}$ are integers.

By the definition of GCD, we have:

$d=ax+by$ for some $x,y\in \mathbb{Z}$

Dividing by $d$ on both sides:

$1=\left(\frac{a}{d}\right)x+\left(\frac{b}{d}\right)y$

From Theorem 18.10, 1 = GCD($\frac{a}{d}$, $\frac{b}{d}$). $◻$

b)
Fix $d=GCD(a,b)$.

Let $r=\frac{a}{d}$ and $s=\frac{b}{d}$. By definition, $r$ and $s$ are integers.

Using part (a) of the proof, we have established that $GCD(\frac{a}{d},\frac{b}{d})=GCD(r,s)=1$.

Therefore, any rational number $\frac{a}{b}$ can be represented as a fraction $\frac{r}{s}$ such that $GCD(r,s)=1$. $◻$

c)
Proof.

We know that $b\ne 0$ as given, but we don't know whether $b$ is positive or negative. $d=GCD(a,b)$ will always be positive, so we need to redefine $s$ to be positive regardless of the sign of $b$.

We can modify the definitions as follows:

1. If $b>0$, let $r=\frac{a}{d}$ and $s=\frac{b}{d}$.
2. If $b<0$, let $r=-\frac{a}{d}$ and $s=-\frac{b}{d}$.

In either case, we guarantee that $s>0$, since $d>0$ and $b$ is either positive (by definition 1) or negative (which then gets multiplied by -1 in definition 2). $◻$

d)
Proof.

We have that $\frac{r}{s}=\frac{r^{\prime }}{s^{\prime }}$, where both fractions are in lowest terms, meaning $GCD(r,s)=GCD(r^{\prime },s^{\prime })=1$.

Assume by way of contradiction that $s\ne s^{\prime }$. Then, both $\frac{r}{s}$ and $\frac{r^{\prime }}{s^{\prime }}$ could be multiplied to get a common denominator $s{s}^{\prime }$, resulting in $\frac{r{s}^{\prime }}{s{s}^{\prime }}=\frac{r^{\prime }s}{s{s}^{\prime }}$.

Since $r$ and $s$ are relatively prime, as are $r^{\prime }$ and $s^{\prime }$, the numerators $r{s}^{\prime }$ and $r^{\prime }s$ are also relatively prime to their respective denominators, or in other words, $GCD(r{s}^{\prime },s{s}^{\prime })=1$ and $GCD(r^{\prime }s,s{s}^{\prime })=1$.

But we already have two fractions that are equal and have the same denominator $s{s}^{\prime }$, and both have their numerator and denominator relatively prime. This implies that the numerators are equal, i.e., $r{s}^{\prime }=r^{\prime }s$.

Now suppose that $s>s^{\prime }$. Then $r{s}^{\prime }=r^{\prime }s<rs$, which is a contradiction. Similarly, if $s<s^{\prime }$, then $r{s}^{\prime }=r^{\prime }s>rs$, which is also a contradiction. Therefore, we must have $s=s^{\prime }$.

Now that it is established that $s=s^{\prime }$, the equation $\frac{r}{s}=\frac{r^{\prime }}{s^{\prime }}$ simplifies to $r=r^{\prime }$. $◻$

E 18.7
a) LCM(12, 18) = 36
b) LCM(21, 35) = 105
c)

Proof.
We aim to prove LCM(a, b) = $\frac{ab}{d}$.
Let $a,b\in \mathbb{Z}$.
Let $d=GCD(a,b)$.
Let $a=a^{\prime }d$ and $b=b^{\prime }d$, where $a^{\prime }$ and $b^{\prime }$ are integers. Since $d$ is the greatest common divisor of $a$ and $b$, it follows that $gcd(a^{\prime },b^{\prime })=1$ per exercise 18.6.

We want to first show that $\frac{ab}{d}$ is a common multiple of both $a$ and $b$.
Substituting $a$ and $b$ with $a^{\prime }d$ and $b^{\prime }d$ respectively, we have

$a^{\prime }{b}^{\prime }d$ is clearly a multiple of both $a=a^{\prime }d$ and $b=b^{\prime }d$ as it contains both as factors.

Let $m$ be any common multiple of $a=a^{\prime }d$ and $b=b^{\prime }d$. Then, $m=a^{\prime }d{b}_1=b^{\prime }d{a}_1=d{a}^{\prime }{b}_1=d{b}^{\prime }{a}_1$ for some integers $a_1$ and $b_1$. As $gcd(a^{\prime },b^{\prime })=1$, we know that $a^{\prime }$ divides $b_1$ and $b^{\prime }$ divides $a_1$. So we can write $b_1=a^{\prime }k$ and $a_1=b^{\prime }k$ for some integer $k$.

Substituting back into the equation $m=d{a}^{\prime }{b}_1=d{b}^{\prime }{a}_1$, we get

Dividing by $k$ on both sides, we get:

Since $k$ is an integer and $m$ is a common multiple of $a$ and $b$, $\frac{m}{k}$ is also a common multiple of $a$ and $b$.

Therefore, $\frac{ab}{d}$ divides every other positive common multiple of $a$ and $b$.

Hence, $\frac{ab}{d}$ is the least common multiple of $a$ and $b$. $◻$