_Posted on April 7, 2024_ ##### Introduction For my first theorem I choose Euclid's Lemma. During the first half of my abstract algebra course, we established the elementary foundations of number theory, where Euclid's lemma played a central role. Euclid's lemma states the following: > [!theorem] **Euclid's Lemma:** _If a prime number $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ must divide at least one of $a$ or $b$._ --- ##### My proof When I set out to write my own proof of this statement I ended up proving the contrapositive statement: If a prime number $p$ divides neither integer $a$ nor $b$, then $p$ does not divide $ab$. Here is my proof: Suppose that $p \nmid a$[^1], and $p \nmid b$. Thus, for all integers $k$, $pk \neq a$, and $pk \neq b$. Let $p_{1}...p_n = a$ be the prime factorization of $a$, and let $p_{n+1}...p_m = b$ be the prime factorization of $b$. Since all of these $p_i$ are integers, and by the [[Fundamental Theorem of Arithmetic]], $p$ cannot be in either prime factorization. Now, notice that $p_1...p_m = ab$. Notice that this prime factorization includes only those primes in the factorizations of $a$ and $b$. Since $p$ is not in either prime factorization, it cannot be in the prime factorization of $ab$. Thus $p \nmid ab$. $\blacksquare$ --- ##### An alternate proof Notice that my proof relies on the Fundamental Theorem of Arithmetic, which establishes the uniqueness of prime factorizations. However, the most common poof of the [[Fundamental Theorem of Arithmetic]] relies directly on Euclid's lemma. So, to prove Euclid's lemma in the way I have done would be circular reasoning by most accounts, so here I will give a more traditional proof. However, in the future, I will explore the [[Fundamental Theorem of Arithmetic]]. I will provide a proof which does not rely on Euclid's lemma, placing my proof on solid ground again. The more traditional proof of Euclid's lemma is as follows: Proof: Suppose that $p \mid ab$. Without loss of generality, suppose that $p \nmid a$. We want to show that $p \mid b$. By the definition of prime, the greatest common divisor of $p$ and $a$ is $1$[^2]. Now, using [[Bézout's Lemma|Bézout's identity]], we have integers $m$ and $n$ such that $pm + an = 1$. Multiplying this by $b$, we get $b(pm + an) = b$. By distributivity, commutativity, and associativity, we get $p(mb) + ab(n) = b$. Notice that $p\mid p(mb)$ and $p \mid ab(n)$. So, for integers $k$ and $l$, $p(k + l)= b$. Since the integers are closed under addition, $p \mid b$. $\blacksquare$ --- [^1]: Note that the notation $a\mid b$ used through this post is used to indicate that $a$ _divides_ $b$. That is, $ak = b$ for some integer $k$ [^2]: Note also that when the greatest common divisor of integers $a$ and $b$ is one ($\text{GCD(a,b)=1})$, $a$ and $b$ are said to be coprime, or relatively prime. #TODO: Also, a number $p$ where $p \mid bc$ implies $p \mid b$ or $p \mid c$ is an altenative definition of prime. The standard definition can be taken to be "irreducible". We have irreducible if and only if prime.