# Integer Combination of Coprime Integers/Proof 3

## Theorem

Two integers are coprime if and only if there exists an integer combination of them equal to $1$:

- $\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$

## Proof

### Sufficient Condition

Let $a, b \in \Z$ be such that $\exists m, n \in \Z: m a + n b = 1$.

Let $d$ be a divisor of both $a$ and $b$.

Then:

- $d \divides m a + n b$

and so:

- $d \divides 1$

Thus:

- $d = \pm 1$

and so:

- $\gcd \set {a, b} = 1$

Thus, by definition, $a$ and $b$ are coprime.

$\Box$

### Necessary Condition

Let $a \perp b$.

Thus they are not both $0$.

Let $S$ be defined as:

- $S = \set {\lambda a + \mu b: \lambda, \mu \in \Z}$

$S$ contains at least one strictly positive integer, because for example:

- $a \in S$ (setting $\lambda = 1$ and $\mu = 0$)
- $b \in S$ (setting $\lambda = 0$ and $\mu = 1$)

By Set of Integers Bounded Below has Smallest Element, let $d$ be the smallest element of $S$ which is strictly positive.

Let $d = \alpha a + \beta b$.

Let $c \in S$, such that $\lambda_0 a + \mu_0 b = c$ for some $\lambda_0, \mu_0 \in \Z$.

By the Division Algorithm:

- $\exists \gamma, \delta \in \Z: c = \gamma d + \delta$

where $0 \le \delta < d$

Then:

\(\ds \delta\) | \(=\) | \(\ds c - \gamma d\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \paren {\lambda_0 a + \mu_0 b} - \gamma \paren {\alpha a + \beta b}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \paren {\lambda_0 - \gamma \alpha} a + \paren {\mu_0 - \gamma \beta} b\) | ||||||||||||

\(\ds \) | \(\in\) | \(\ds S\) |

But we have that $0 \le \delta < d$.

We have defined $d$ as the smallest element of $S$ which is strictly positive

Hence it follows that $\delta$ cannot therefore be strictly positive itself.

Hence $\delta = 0$ and so $c = \gamma d$.

That is:

- $d \divides c$

and so the smallest element of $S$ which is strictly positive is a divisor of both $a$ and $b$.

But $a$ and $b$ are coprime.

Thus it follows that, as $d \divides 1$:

- $d = 1$

and so, by definition of $S$:

- $\exists m, n \in \Z: m a + n b = 1$

$\blacksquare$

## Sources

- 1968: Ian D. Macdonald:
*The Theory of Groups*... (previous) ... (next): Appendix: Elementary set and number theory