Greatest Common Divisors and Their Properties

Let ${𝑎}^{\prime }=𝑎/𝑑$ and ${𝑏}^{\prime }=𝑏/𝑑$, and let $𝑒=\gcd ({𝑎}^{\prime },{𝑏}^{\prime })$. We want to show that $𝑒=1$.

Since $𝑒∣{𝑎}^{\prime }$, we have $𝑒𝑑∣{𝑎}^{\prime }𝑑=𝑎$. Similarly, $𝑒𝑑∣𝑏$. Thus $𝑒𝑑$ is a common divisor of $𝑎$ and $𝑏$. But $𝑑$ is the greatest common divisor, so $𝑑𝑒\leq 𝑑$. Dividing both sides by $𝑑$, we obtain $𝑒\leq 1$, and hence $𝑒=1$, since $𝑒$ is positive.

The integers $𝑝=𝑎/\gcd (𝑎,𝑏)$ and $𝑞=𝑏/\gcd (𝑎,𝑏)$ are as desired.

Let $𝑑=\gcd (𝑎,𝑏)$ and $𝑒=\gcd (𝑎+𝑐𝑏,𝑏)$. We shall show that $𝑑=𝑒$ by showing both $𝑑\leq 𝑒$ and $𝑒\leq 𝑑$.

Since $𝑑∣𝑎$ and $𝑑∣𝑏$, by Proposition 1.11, $𝑑∣𝑎+𝑐𝑏$. Thus $𝑑$ is a common divisor of $𝑎+𝑐𝑏$ and $𝑏$. It then follows that $𝑑\leq 𝑒$.

On the other hand, since $𝑒∣𝑎+𝑐𝑏$ and $𝑒∣𝑏$, again by Proposition 1.11 we have $𝑒∣𝑎$, since $𝑎=(𝑎+𝑐𝑏)-𝑐𝑏$. Therefore $𝑒$ is a common divisor of $𝑎$ and $𝑏$, and hence $𝑒\leq 𝑑$.

Therefore $𝑑=𝑒$.

Let $𝑆$ be the set of all positive linear combinations of $𝑎$ and $𝑏$, that is,

$$𝑆=\{𝑚𝑎+𝑛𝑏:𝑚,𝑛\in \mathbb{Z}\}\cap {\mathbb{Z}}^{+}.$$

We want a least element of $𝑆$. Note that ${𝑎}^{2}+{𝑏}^{2}$ is a linear combination of $𝑎$ and $𝑏$, and ${𝑎}^{2}+{𝑏}^{2}>0$ since $𝑎$ and $𝑏$ are not both $0$. Thus ${𝑎}^{2}+{𝑏}^{2}\in 𝑆$, so $𝑆\neq \emptyset$. Since $𝑆$ is a nonempty subset of ${\mathbb{Z}}^{+}$, the well-ordering principle gives a least element $𝑑\in 𝑆$. And $𝑑$ can be written as $𝑑=𝑚𝑎+𝑛𝑏$ for some $𝑚,𝑛\in \mathbb{Z}$.

Let ${𝑑}^{\prime }=\gcd (𝑎,𝑏)$. We want to show $𝑑={𝑑}^{\prime }$.

Because ${𝑑}^{\prime }∣𝑎$ and ${𝑑}^{\prime }∣𝑏$, by Proposition 1.11 we have ${𝑑}^{\prime }∣𝑚𝑎+𝑛𝑏=𝑑$. Since $𝑑>0$, we have ${𝑑}^{\prime }\leq 𝑑$.

For the other side of the inequality, we plan to show that $𝑑$ divides both $𝑎$ and $𝑏$. By the division algorithm Theorem 1.5, we have

$$𝑎=𝑑𝑞+𝑟,\quad 𝑞,𝑟\in \mathbb{Z}\, \text{ with }\, 0\leq 𝑟<𝑑.$$

Substitute $𝑑=𝑚𝑎+𝑛𝑏$:

$$𝑎=(𝑚𝑎+𝑛𝑏)𝑞+𝑟=(𝑚𝑞)𝑎+(𝑛𝑞)𝑏+𝑟.$$

Rearrange:

$$(1-𝑚𝑞)𝑎+(-𝑛𝑞)𝑏=𝑟.$$

If $𝑟>0$, then $𝑟\in 𝑆$. That would contradict the fact that $𝑑$ is the least element of $𝑆$, since $𝑟<𝑑$. Therefore $𝑟=0$, and hence $𝑑∣𝑎$. The same argument shows that $𝑑∣𝑏$. Thus $𝑑$ is a common divisor of $𝑎$ and $𝑏$, so by definition $𝑑\leq {𝑑}^{\prime }$.

We have shown both ${𝑑}^{\prime }\leq 𝑑$ and $𝑑\leq {𝑑}^{\prime }$, and therefore $𝑑={𝑑}^{\prime }=\gcd (𝑎,𝑏)$.

By Theorem 3.3, $\gcd (𝑎,𝑏)$ is the least positive linear combination of $𝑎$ and $𝑏$, and hence $\gcd (𝑎,𝑏)$ can be written as $𝑚𝑎+𝑛𝑏$ for some integers $𝑚$ and $𝑛$.

($⟹$). Suppose $𝑎$ and $𝑏$ are coprime. Then $\gcd (𝑎,𝑏)=1$, so by Corollary 3.2 there exist $𝑚,𝑛\in \mathbb{Z}$ such that $𝑚𝑎+𝑛𝑏=\gcd (𝑎,𝑏)=1$.

($⟸$). Suppose $𝑚𝑎+𝑛𝑏=1$. Clearly $𝑎$ and $𝑏$ are not both $0$. Let $𝑆$ be the set of all positive linear combinations of $𝑎$ and $𝑏$. We have $1\in 𝑆$. By Theorem 3.3, $\gcd (𝑎,𝑏)$ is the least element of $𝑆$, and hence $\gcd (𝑎,𝑏)\leq 1$. Therefore $\gcd (𝑎,𝑏)=1$.

If $𝑎=0$, then $\gcd (0,𝑏)=1$, so $|𝑏|=1$ and $𝑏=\pm 1$. The hypothesis $0∣𝑏𝑐$ means $𝑏𝑐=0$, hence $𝑐=0$, and so $0∣𝑐$.

If $𝑎<0$, then $\gcd (|𝑎|,𝑏)=1$, and $𝑎∣𝑏𝑐$ if and only if $|𝑎|∣𝑏𝑐$. The case of a positive first argument, applied to $|𝑎|$, gives $|𝑎|∣𝑐$, and hence $𝑎∣𝑐$. We may therefore assume that $𝑎>0$.

By Theorem 1.5, we can write

$$𝑐=𝑎𝑞+𝑟$$

for some $𝑞,𝑟\in \mathbb{Z}$ with $0\leq 𝑟<𝑎$. Then

$$𝑏𝑐=𝑎𝑏𝑞+𝑏𝑟.$$

Since $𝑎∣𝑏𝑐$ and $𝑎∣𝑎𝑏𝑞$, we have $𝑎∣𝑏𝑟$.

Because $\gcd (𝑎,𝑏)=1$, by Corollary 3.3 there exist $𝑚,𝑛\in \mathbb{Z}$ such that $𝑚𝑎+𝑛𝑏=1$. Multiplying through by $𝑟$ gives

$$𝑚𝑎𝑟+𝑛𝑏𝑟=𝑟.$$

Note that $𝑎∣𝑚𝑎𝑟$ and $𝑎∣𝑛𝑏𝑟$. It then follows that $𝑎∣𝑟$. But $0\leq 𝑟<𝑎$, so $𝑟=0$, which means that $𝑎∣𝑐$.

It is easy to verify that $𝑥={𝑥}_{0}+𝑏𝑡$ and $𝑦={𝑦}_{0}-𝑎𝑡$ do solve (3.3).

Conversely, suppose that $(𝑥,𝑦)$ is a solution of (3.3). We have

$$\begin{aligned}𝑎𝑥+𝑏𝑦 & =1, \\ 𝑎{𝑥}_{0}+𝑏{𝑦}_{0} & =1.\end{aligned}$$

Subtracting these equations yields

$$𝑎(𝑥-{𝑥}_{0})+𝑏(𝑦-{𝑦}_{0})=0.$$

Note that $𝑏∣𝑎(𝑥-{𝑥}_{0})$, because $𝑏∣0$ and $𝑏∣𝑏(𝑦-{𝑦}_{0})$. Since $\gcd (𝑎,𝑏)=1$, by Proposition 3.1 we have $𝑏∣𝑥-{𝑥}_{0}$. Then there exists $𝑡\in \mathbb{Z}$ such that $𝑥-{𝑥}_{0}=𝑏𝑡$. Substitute into the subtracted equation:

$$𝑎(𝑏𝑡)+𝑏(𝑦-{𝑦}_{0})=0.$$

Since $𝑏\neq 0$, we obtain $𝑦-{𝑦}_{0}=-𝑎𝑡$. Therefore $𝑥={𝑥}_{0}+𝑏𝑡$ and $𝑦={𝑦}_{0}-𝑎𝑡$.

Let ${𝑎}^{\prime }=𝑎/𝑑$ and ${𝑏}^{\prime }=𝑏/𝑑$. We have $\gcd ({𝑎}^{\prime },{𝑏}^{\prime })=1$, and neither ${𝑎}^{\prime }$ nor ${𝑏}^{\prime }$ is $0$.

Since $𝑎={𝑎}^{\prime }𝑑$ and $𝑏={𝑏}^{\prime }𝑑$, the equation (3.4) is $𝑑({𝑎}^{\prime }𝑥+{𝑏}^{\prime }𝑦)=𝑑$. As $𝑑\neq 0$, this is equivalent to ${𝑎}^{\prime }𝑥+{𝑏}^{\prime }𝑦=1$. Thus the solutions of (3.4) are precisely the solutions of ${𝑎}^{\prime }𝑥+{𝑏}^{\prime }𝑦=1$.

Let $({𝑥}_{0},{𝑦}_{0})$ be a particular solution of (3.4). Then it is a particular solution of ${𝑎}^{\prime }𝑥+{𝑏}^{\prime }𝑦=1$. By Proposition 3.2, the solutions are

$$\begin{aligned}𝑥 & ={𝑥}_{0}+{𝑏}^{\prime }𝑡, \\ 𝑦 & ={𝑦}_{0}-{𝑎}^{\prime }𝑡,\end{aligned}$$

where $𝑡\in \mathbb{Z}$. Since ${𝑏}^{\prime }=\frac{𝑏}{𝑑}$ and ${𝑎}^{\prime }=\frac{𝑎}{𝑑}$, this is

$$\begin{aligned}𝑥 & ={𝑥}_{0}+\left(\frac{𝑏}{𝑑}\right)𝑡, \\ 𝑦 & ={𝑦}_{0}-\left(\frac{𝑎}{𝑑}\right)𝑡.\end{aligned}$$

We first show that $𝑎\mathbb{Z}+𝑏\mathbb{Z}\subseteq \gcd (𝑎,𝑏)\mathbb{Z}$. Let $𝑑\in 𝑎\mathbb{Z}+𝑏\mathbb{Z}$. Then $𝑑=𝑚𝑎+𝑛𝑏$ for some $𝑚,𝑛\in \mathbb{Z}$. We have $𝑎={𝑎}^{\prime }\gcd (𝑎,𝑏)$ and $𝑏={𝑏}^{\prime }\gcd (𝑎,𝑏)$ for some ${𝑎}^{\prime },{𝑏}^{\prime }\in \mathbb{Z}$. Thus $𝑑=(𝑚{𝑎}^{\prime }+𝑛{𝑏}^{\prime })\gcd (𝑎,𝑏)$, and hence $𝑑\in \gcd (𝑎,𝑏)\mathbb{Z}$. Therefore $𝑎\mathbb{Z}+𝑏\mathbb{Z}\subseteq \gcd (𝑎,𝑏)\mathbb{Z}$.

Next we show that $\gcd (𝑎,𝑏)\mathbb{Z}\subseteq 𝑎\mathbb{Z}+𝑏\mathbb{Z}$. For any $𝑑\in \gcd (𝑎,𝑏)\mathbb{Z}$, we have $𝑑=𝑘\gcd (𝑎,𝑏)$. By Theorem 3.3, $\gcd (𝑎,𝑏)\in 𝑎\mathbb{Z}+𝑏\mathbb{Z}$, and hence $\gcd (𝑎,𝑏)=𝑚𝑎+𝑛𝑏$ for some $𝑚,𝑛\in \mathbb{Z}$. Therefore $𝑑=𝑘𝑚𝑎+𝑘𝑛𝑏\in 𝑎\mathbb{Z}+𝑏\mathbb{Z}$, and hence $\gcd (𝑎,𝑏)\mathbb{Z}\subseteq 𝑎\mathbb{Z}+𝑏\mathbb{Z}$.

($⟹$). Let $𝑑=\gcd (𝑎,𝑏)$. The first property holds by definition. Let $𝑐\in \mathbb{Z}$ be such that $𝑐∣𝑎$ and $𝑐∣𝑏$. By Theorem 3.3, there exist $𝑚,𝑛\in \mathbb{Z}$ such that $𝑑=𝑚𝑎+𝑛𝑏$. Then, by Proposition 1.11, $𝑐∣𝑚𝑎+𝑛𝑏=𝑑$. Thus the second property holds.

($⟸$). Let ${𝑑}^{\prime }=\gcd (𝑎,𝑏)$. By the property of $𝑑$, we have ${𝑑}^{\prime }∣𝑑$. Thus $𝑑$ can be written as $𝑑={𝑑}^{\prime }𝑘$ for some $𝑘\in {\mathbb{Z}}^{+}$. ($𝑑>0$.) Meanwhile, since $𝑑$ is a common divisor of $𝑎$ and $𝑏$, we have $𝑑\leq {𝑑}^{\prime }$. It then follows that $𝑘\leq 1$, and hence $𝑘=1$. Therefore ${𝑑}^{\prime }=𝑑$.

Let $𝑑=\gcd ({𝑎}_{1},\ldots ,{𝑎}_{𝑛})$ and ${𝑑}^{\prime }=\gcd ({𝑎}_{1},\ldots ,\gcd ({𝑎}_{𝑛-1},{𝑎}_{𝑛}))$.

Since $𝑑∣{𝑎}_{𝑛-1}$ and $𝑑∣{𝑎}_{𝑛}$, by Theorem 3.5 we have $𝑑∣\gcd ({𝑎}_{𝑛-1},{𝑎}_{𝑛})$. Hence $𝑑$ is a common divisor of ${𝑎}_{1},{𝑎}_{2},\ldots ,\gcd ({𝑎}_{𝑛-1},{𝑎}_{𝑛})$. It then follows that $𝑑\leq {𝑑}^{\prime }$.

On the other hand, since ${𝑑}^{\prime }∣\gcd ({𝑎}_{𝑛-1},{𝑎}_{𝑛})$, and $\gcd ({𝑎}_{𝑛-1},{𝑎}_{𝑛})$ divides both ${𝑎}_{𝑛-1}$ and ${𝑎}_{𝑛}$, transitivity gives that ${𝑑}^{\prime }$ divides both ${𝑎}_{𝑛-1}$ and ${𝑎}_{𝑛}$. Thus ${𝑑}^{\prime }$ is a common divisor of ${𝑎}_{1},\ldots ,{𝑎}_{𝑛}$, and hence ${𝑑}^{\prime }\leq 𝑑$.

Therefore $𝑑={𝑑}^{\prime }$.

Because $\gcd (𝑎,𝑏)=1$, a small tweak of the solutions in Bézout’s identity Proposition 3.2 gives the solutions of

$$𝑎𝑥-𝑏𝑦=-1$$

as

$$\begin{aligned}𝑥 & ={𝑥}_{0}+𝑏𝑡, \\ 𝑦 & ={𝑦}_{0}+𝑎𝑡,\end{aligned}$$

where $({𝑥}_{0},{𝑦}_{0})$ is a particular solution and $𝑡\in \mathbb{Z}$.

Let $𝑡=\lfloor (𝑛-{𝑥}_{0})/𝑏\rfloor$ and $𝑞={𝑥}_{0}+𝑏𝑡$, and let $𝑝$ be determined accordingly. We will show that $𝑝$ and $𝑞$ are as desired.

We have

$$𝑡\leq \frac{𝑛-{𝑥}_{0}}{𝑏}<𝑡+1.$$

Rearrange:

$$𝑛-𝑏<{𝑥}_{0}+𝑏𝑡\leq 𝑛.$$

It then follows that

$$\begin{aligned}𝑞={𝑥}_{0}+𝑏𝑡 & \leq 𝑛 \\ 𝑏+𝑞={𝑥}_{0}+𝑏𝑡+𝑏 & >𝑛.\end{aligned}$$

Thus $𝑞\leq 𝑛$, as the definition of a Farey sequence requires, and $𝑏+𝑞>𝑛$, which is the third property.

Recall that

This is exactly the second property. We still need $𝑝$ to be valid. We have

$$𝑝=\frac{𝑎𝑞+1}{𝑏}=\left(\frac{𝑎}{𝑏}\right)𝑞+\frac{1}{𝑏}<𝑞+\frac{1}{𝑏}.$$

Here $𝑎/𝑏<1$ is the given condition, so $𝑝\leq 𝑞$. And from (3.5),

$$𝑎𝑞-𝑏𝑝=-1<0.$$

Then $𝑎𝑞<𝑏𝑝$, and hence $𝑎/𝑏<𝑝/𝑞$. (Both $𝑏$ and $𝑞$ are greater than $0$, as we know.) This shows that the first property holds, and also that $𝑝\geq 0$, so $𝑝/𝑞$ is indeed a term of ${𝔉}_{𝑛}$.

Thus all three properties hold, and $𝑝/𝑞$ lies in ${𝔉}_{𝑛}$.

We prove by contradiction. Assume that $𝑐/𝑑$ is the term consecutive to $𝑎/𝑏$, and that it is not $𝑝/𝑞$. Then $𝑐/𝑑$ sits strictly between the fraction we started with and the fraction we built:

$$\frac{𝑎}{𝑏}<\frac{𝑐}{𝑑}<\frac{𝑝}{𝑞}.$$

A strict inequality of two fractions with positive denominators is a positive cross-difference, and a positive integer is at least $1$. The first inequality implies $𝑎𝑑<𝑏𝑐$, so $𝑏𝑐-𝑎𝑑>0$. The difference is an integer, so $𝑏𝑐-𝑎𝑑\geq 1$. The same argument, from $𝑐/𝑑<𝑝/𝑞$, gives $𝑑𝑝-𝑐𝑞\geq 1$.

The two gaps are now integers we can weight. Multiply the first by $𝑞$ and the second by $𝑏$, and add. This is the step the argument turns on. The terms $𝑏𝑐𝑞$ cancel, and the second property of Lemma 3.2 turns what remains into exactly $𝑑$:

$$\begin{aligned}𝑞(𝑏𝑐-𝑎𝑑)+𝑏(𝑑𝑝-𝑐𝑞) & =𝑏𝑐𝑞-𝑎𝑑𝑞+𝑏𝑑𝑝-𝑏𝑐𝑞 \\ & =𝑑(𝑏𝑝-𝑎𝑞) \\ & =𝑑,\end{aligned}$$

where the last equality follows from $𝑎𝑞-𝑏𝑝=-1$.

The same sum is large for a different reason. Each gap is at least $1$, and the third property of Lemma 3.2 says $𝑏+𝑞>𝑛$, so

$$𝑞(𝑏𝑐-𝑎𝑑)+𝑏(𝑑𝑝-𝑐𝑞)\geq 𝑞+𝑏>𝑛.$$

The left side equals $𝑑$, so $𝑑>𝑛$. Then $𝑐/𝑑$ cannot be a term in ${𝔉}_{𝑛}$: a contradiction. Therefore the original assumption is false, and $𝑐/𝑑=𝑝/𝑞$.

Both extra properties of Lemma 3.2 are spent once, and neither is decorative. $𝑎𝑞-𝑏𝑝=-1$ is what collapses the weighted gaps to $𝑑$, rather than to some larger multiple of $𝑑$. $𝑏+𝑞>𝑛$ is what makes that $𝑑$ too big for ${𝔉}_{𝑛}$.

Since $𝑎/𝑏<1$, by Lemma 3.2 we may construct $𝑝/𝑞$ in ${𝔉}_{𝑛}$, larger than $𝑎/𝑏$, such that $𝑎𝑞-𝑏𝑝=-1$ and $𝑏+𝑞>𝑛$. Then, by Lemma 3.3, we must have $𝑐/𝑑=𝑝/𝑞$. Both fractions are irreducible, so an equality of fractions is an equality of numerators and of denominators: $𝑐=𝑝$ and $𝑑=𝑞$.

By Theorem 3.6, we have

$$\begin{aligned}𝑎𝑑-𝑏𝑐 & =-1 \\ 𝑐𝑓-𝑑𝑒 & =-1.\end{aligned}$$

We may solve for $𝑐$ and $𝑑$ in terms of $𝑎$, $𝑏$, $𝑒$, and $𝑓$. We have

$$\begin{aligned}𝑐 & =\frac{𝑎+𝑒}{𝑏𝑒-𝑎𝑓} \\ 𝑑 & =\frac{𝑏+𝑓}{𝑏𝑒-𝑎𝑓}.\end{aligned}$$

Divide, and we are done:

$$\frac{𝑐}{𝑑}=\frac{𝑎+𝑒}{𝑏+𝑓}.$$