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. 
