Euclid's Lemma
If
\[a | bc\]
with the greatest common divisor of \[a, \; b\]
equal to 1, then \[a | c\]
.Proof
\[a | bc\]
and the greatest common divisor of \[a, \; b\]
eqials 1, so there exist integers \[k, \; m, \; n\]
such that \[bc=ka, \; ma+nb=1\]
.Multiply though by
\[c\]
to give \[mac+nbc=c\]
and use \[bc=ka\]
to give\[mac+nka=c \rightarrow a(mc+nk)=c \rightarrow a | c\]
