# Integer Combination of Coprime Integers/Proof 1

## 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

 $\ds a$ $\perp$ $\ds b$ $\ds \leadsto \ \$ $\ds \gcd \set {a, b}$ $=$ $\ds 1$ Definition of Coprime Integers $\ds \leadsto \ \$ $\ds \exists m, n \in \Z: m a + n b$ $=$ $\ds 1$ Bézout's Lemma

Then we have:

 $\ds \exists m, n \in \Z: m a + n b$ $=$ $\ds 1$ $\ds \leadsto \ \$ $\ds \gcd \set {a, b}$ $\divides$ $\ds 1$ Set of Integer Combinations equals Set of Multiples of GCD $\ds \leadsto \ \$ $\ds \gcd \set {a, b}$ $=$ $\ds 1$ $\ds \leadsto \ \$ $\ds a$ $\perp$ $\ds b$ Definition of Coprime Integers

$\blacksquare$