# Integer Combination of Coprime Integers/Proof 2

## 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 {a m + b n: m, n \in \Z}$

$S$ contains at least one strictly positive integer, because for example $a^2 + b^2 \in S$.

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

Let $d = a x + b y$.

It remains to be shown that $d = 1$.

By the Division Theorem:

- $a = d q + r$ where $0 \le r < d$

Then:

\(\displaystyle r\) | \(=\) | \(\displaystyle a - d q\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle a - \paren {a x + b y} q\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle a \paren {1 - x q} + b \paren {- y q}\) | |||||||||||

\(\displaystyle \) | \(\in\) | \(\displaystyle S\) |

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

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

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

Hence $r = 0$ and so $a = d q$.

That is:

- $d \divides a$

By a similar argument:

- $d \divides b$

and so $d$ is a common divisor of both $a$ and $b$.

But the GCD of $a$ and $b$ is $1$.

Thus it follows that, as $d \in S$:

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

$\blacksquare$

## Sources

- 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Lemma $1$