## Proof of Condition For Integers to be Relatively Prime

Integers

\[a, \; b\]

are relatively prime if and only if there exist integers \[m, \; n\]

such that \[ma+nb=1\]

.Proof

If

\[a, \; b\]

are relatively prime, then their greatest common divisor is 1, so by this theorem there exist integers \[m, \; n\]

such that \[ma+nb=1\]

.Conversely suppose that there are integers

\[m, \; n\]

\[ma+nb=1\]

. Let \[d\]

be the greatest common divisor of \[a, \; b\]

, then \[d | a \rightarrow d | ma, \; d | b \rightarrow d | nb \rightarrow d | ma+nb=1 \rightarrow d | 1\]

.Hence

\[d=1\]

and \[a, \; b\]

are relatively prime.