_Posted on April 9, 2024_ _Updated on February 26, 2025_ ##### Introduction In the spirit of giving more strength to our exploration of [[Euclid's Lemma]], we aim to eventually explore [[Bézout's Lemma]] and the [[Fundamental Theorem of Arithmetic]] (FTA), providing a proof of the FTA that does not rely on [[Euclid's Lemma]]. An exploration of Euclid's division lemma is crucial to this development. Here is the statement of Euclid's Division Lemma: > [!theorem] **Euclid's Division Lemma:** _Given two integers $a$ and $b$, with $b \neq 0$, there exist unique integers $q$ and $r$ such that $a=bq + r$ and $0 \leq r < |b|$._ Note that $a$ is called the dividend, $b$ is called the divisor, $q$ is called the quotient, and $r$ is called the remainder. --- ##### Prerequisites I have developed a proof, which makes use of the well ordering principle, a fundamental property of the natural numbers, and one crucial lemma which relates the magnitude of the divisor and dividend (divisor magnitude lemma). The well ordering principle states that every nonempty subset of the natural numbers contains a least element. This property will be accepted without proof. ^ee5ece > [!theorem] **divisor magnitude lemma:** _The divisor magnitude lemma states that if $b \mid a$ and $a \neq 0$, then $|b| \leq |a|$._ The proof of this is simple: ^40f373 By the definition of divisibility, $bc = a$ for some integer $c$. Since $a \neq 0$, both $b$ and $c$ are nonzero and so $|c| \geq 1$. Thus $|a| = |b|*|c| \geq |b|*1 = |b|$ $\blacksquare$ --- ##### My Proof Proof of Euclid's Division Lemma: First, we will show the existence of $q$ and $r$ such that $a = bq + r$. We assume that $b > 0$, since in this case, we can apply the statement to $-b > 0$ and flip the sign of $q$. Let $S$ be the set of all nonnegative integers $y$ that satisfy $a = bx + y$ for integer $x$. Note that $S$ is nonempty, since for nonnegative $a$, $y = a \implies b\cdot 0 + a = a$. For Negative $a$, we have $y = a(1 - b) \implies ba + a(1-b) = ba + a - ab = a$ (note that $1 - b \leq 0$ so that $y \geq 0$). Since $S$ is always nonempty, it has a least element $y = r$ by the well ordering principle. This $r$ is associated with somhe $x = q$. We will show by contradiction that $0 \leq r < b$. Suppose that $r$ does not satisfy this inequality and so $r \geq b$. Then, $r - b \geq 0$. So, $a = bq + r = b(q + 1) + (r - b)$. Since $r - b < r$, and $r - b$ is in $S$, $r - b$ is an element of $S$ less than the least element of $S$, a contradiction. Thus, $r$ must satisfy the inequality $0 \leq r < b$ (we established above that $r > 0$). Now, we need to demonstrate the uniqueness of $q$ and $r$. Assume that there are two such pair of $q$ and $r$, such that $a = bq + r = bq'+r'$ satisfying $0 \leq r < b$ and $0 \leq r' < b$. Since $r$ and $r'$ are both in the range $[0,b-1]$, the maximum distance between $r$ and $r'$ is $b -1$, or notationally, $|r' - r| \leq b -1$. This implies that $|r - r'| < |b|$. Subtracting two equations, we have $b(q - q') + (r - r')$ which implies that $b(q-q') = r'-r$. This implies that $b \mid r' - r$. This implies (by the divisor magnitude lemma) that $|b|<|r'-r|$. A contradiction $\blacksquare$. --- _Added on April 14, 2024_ _Updated on May 20, 2025_ Computing the quotient $q$ and remainder $r$ is useful in many contexts. To do this, we can use an [[Integer Division Algorithms|integer division algorithm]]. ---