Euclid's Lemma

Theorem 4:  Euclid's Lemma

If a prime $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ divides $a$ or $p$ divides $b$

Proof:

(1)  Assume that $p | ab$ but $p \nmid a$

(2)  From Bezout's Identity, there exists $r,s$ such that $rp + sa = 1$

(3)  Multiply both sides by $b$ to get:  $rpb + sab = b$

(4)  Since $p | ab$, it follows that $p | b$

Corollary 4.1:  Euclid's Generalized Lemma

If a prime $p$ divides $a_1a_2\dots{a_m}$, then $p$ divides $a_i$ where $1 \le i \le m$

Proof:

(1)  Base Case:  The base case is Euclid's Lemma.  If $p | a_1a_2$, then $p | a_1$ or $p | a_2$

(2)  Assume that up to $n$ if $p | a_1a_2\dots{a_n}$, then $p|a_i$ with $1 \le i \le n$

(3)  Let $b = a_1a_2\dots{a_n}$.  

(4)  Inductive Case:  From Euclid's Lemma, if $p | ba_{n+1}$, then $p | b$ or $p|a_{n+1}$.