----- > [!proposition] Proposition. ([[Euclid's Lemma]]) > Let $a,b \in \zz$ with $b>0$. If $p$ is a [[prime number|prime]] that [[divides]] $ab$, then $p$ [[divides]] $a$ or $p$ divides $b$. ^51fe25 > [!proof]- Proof. ([[Euclid's Lemma]]) > Suppose $p$ is a [[prime number]] that divides $ab$ but does not [[divides|divide]] $a$; we show this necessitates $p | b$. $p$ is [[prime number|prime]]; only $(\pm)1$ and $(\pm)p$ [[divides|divide]] it. Hence $\gcd(a,p)$ is $1$ or $p$. By assumption $p \nmid b$ so [[greatest common divisor]]$(a,p)=1$ hence $a,p$ [[relatively prime integers|relatively prime]]. By [[GCD is a linear combination]] this means there exist $s,t \in \zz$ such that $as + pt = 1$. Then $b=abs + pbt$ and since $p$ [[divides]] the RHS it [[divides]] $b$. ^8b741c ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```