_Posted on November 02, 2024_ ##### Introduction #TODO Make this post more narrative > [!definition] Given two integers $a$ and $b$, we say that $a$ divides $b$, or $a \mid b$ if and only if $an = b$ for some integer $n$. --- ##### Partial ordering over the positive integers > [!theorem] **Theorem:** _The divides binary relation is reflexive. (i.e. For all integers $a$, $a \mid a$)._ Proof: Suppose we have an arbitrary integer $a$. We have $a(1) = a$, so that $a \mid a$. $\blacksquare$ > [!theorem] **Theorem:** _The divides binary relation is transitive. (i.e. If $a \mid b$ and $b \mid c$, then $a \mid c$)._ Proof: Suppose, for integers $a,b,$ and $c$, that $a \mid b$ and $b \mid c$. By the definition of $\mid$, $an = b$ for some integer $n$, and $bm = c$ for some integer $m$. Then, $c = (an)m$. By the associativity of multiplication for integers, $c = a(nm)$. Since $nm$ is an integer, (because the integers are closed under multiplication) $c = ak$ for $k = nm$. By the definition of $\mid$, $a \mid c$. This is the desired result. $\blacksquare$ > [!theorem] **Theorem:** _For positive integers $a,b,$ the divides binary relation is antisymmetric. (i.e. If $a \mid b$ and $b \mid a$, then $a = b,$ for positive integers $a$ and $b$)._ Proof: Suppose we have positive integers $a$ and $b$ such that $a \mid b$ and $b \mid a$. Then, $an = b$ for some integer $n$, and $bm = a$ for some integer $m$. Substituting $an$ for $b$, we have $(an)m = a(nm) = a$. Thus, $nm = 1$, so that $n = 1$ and $m = 1$. Substituting $1$ for $n$ and $m$, $a = b$. $\blacksquare$ > [!theorem] **Theorem:** _The divides binary relation is a partial ordering over the positive integers._ Proof: The result follows directly from the divides binary relation being reflexive, transitive, and antisymmetric. $\blacksquare$ --- ##### Algebra of $\mid$ (divides) > [!theorem] **Closure of divisibility under addition:** _For integers $a,b,c$, if $a \mid b$ and $a \mid c$, then $a \mid b + c$._ Proof: Suppose that we have integers $a,b,c$ such that $a \mid b$ and $a \mid c$. Then we have integers $n,m$ such that $an = b$ annd $am = c$. Thus, $b + c = an+am=a(n+m)$. Since $n+m$ is an integer (because the integers are closed under subtraction) $b + c = ak$ for $k + n + m$. This is the desired result. $\blacksquare$ > [!theorem] **Closure of divisibility under subtraction:** For integers $a,b,c$, if $a \mid b$ and $a \mid c$, then $a \mid b - c$. Proof: Suppose that we have integers $a,b,c$ such that $a \mid b$ and $a \mid c$. Observe that $b - c = b + (-c)$. Since $a \mid c$, we have $an = c$ for some integer $n$. But $a(-n) = -c$, so that $a \mid -c$. Since $-c$ is an integer, we have $a \mid b + (-c)$ by closure of divisibility under addition, which implies that $a \mid b - c$. $\blacksquare$ > [!theorem] **Closure of divisibility under multiplication:** _For integers $a,b,$ if $a \mid b,$ then $a \mid bc$ for any integer $c$._ Proof: Suppose we have integers $a,b$ such that $a \mid b$. Then, we have $an = b$ for some integer $n$. Then for an arbitrary integer $c$, we have $bc = (an)c = a(nc)$, so that $bc = ak$ for $k = nc$. This is the desired result. $\blacksquare$ > [!Theorem] **Divisibility of Powers:** For integers $a,b,$ if $a \mid b$, then $a \mid b^k$ for all positive integers $k$. Proof: Suppose we have integers $a,b$ such that $a \mid b$. We prove this by mathematical induction. The base case $a \mid b^1$ is trivial, since $b^1 = b$. Now, suppose for some integer $k$ such that $0 <k,$ $a \mid b^k,$ then, $an = b^k$ for some integer $n$. But we have $b^{k+1} = b^kb=(an)b = a(nb) = a(m)$ for $m = nb$. This is the desired result. $\blacksquare$ > [!theorem] **Theorem:** For integers $a,b,c,$ if $a\mid bc$, and $\text{GCD}(a,b) = 1$ ($a$ and $b$ are coprime), then $a \mid c$. Proof: Suppose that we have integers $a,b,c$ such that $a \mid bc$, and $\text{GCD}(a,b) = 1$. Since $a \mid bc$, there exists an integer $n$ such that $an = bc$. By the [[Fundamental Theorem of Arithmetic]], we can write $a, b,$ and $c$ in terms of their unique prime factorizations: $a = p_1^{\alpha_1}\cdots p_t^{\alpha_t},\quad b=q_1^{\beta_1}\cdots q_k^{\beta_k}\quad c=r_1^{\gamma_1}\cdots r_s^{\gamma_s},$ where $p_i,$ $q_j,$ and $r_l$ are primes, and, since $\text{GCD}(a,b) = 1$, none of the prime $p_i$ appear among the primes $q_j$. Now, we substitute the prime factorizations of $a,$ $b,$ and $c$ into the equation $an = bc:$ $(p_1^{\alpha_1}\cdots p_t^{\alpha_t})n=(q_1^{\beta_1}\cdots q_k^{\beta_k})(r_1^{\gamma_1}\cdots r_s^{\gamma_s})$Since the prime factors of $a$ do not apear in $b$, all the primes $q_j$ in $b$ must be factors of $n$ for the equality to hold. Thus, $n$ can be written as:$n = q_1^{\beta_1}\cdots q_k^{\beta_k}m$where $m$ is an integer containing the prime factors in $n$ which are not in $b$. Substituting the factorization of $n$ into the equation $an = bc,$ we have$(p_1^{\alpha_1}\cdots p_t^{\alpha_t})(q_1^{\beta_1}\cdots q_k^{\beta_k})m=(q_1^{\beta_1}\cdots q_k^{\beta_k})(r_1^{\gamma_1}\cdots r_s^{\gamma_s}).$ Dividing both sides by $b$, we get$(p_1^{\alpha_1}\cdots p_t^{\alpha_t})m = r_1^{\gamma_1}\cdots r_s^{\gamma_s}.$Substituting $a$ and $c$ back in, we get $am = c.$Since $m$ is an integer, we have $a \mid c$, which is the desired result. $\blacksquare$ The common proof of this result uses [[Bézout's Lemma]]. --- See also, [[Euclid's Lemma]], [[Euclid's Division Lemma#^40f373|The Divisor Magnitude Lemma]].