\(\textbf{Least-integer Principle: }\)A nonempty set of integers that is bounded below contains a smallest element.
\(\textbf{Greatest-integer Principle: }\)A nonempty set of integers that is bounded above contains a largest element.
\(\textbf{Definition: }\) We say \(a\) divides \(b\) (written \(a\;|\; b\)) if and only if there is an integer \(k\) such that \(b = ka\).
\(\textbf{Definition: }\) We say \(d\) is the greatest common divisor of \(a\) and \(b\) (written \(d = (a, b)\text{ or }d=\gcd(a, b)\)) if and only if
Note. \((0, 0)\) is not defined since there is no greatest common divisor of \(0\) and \(0\). \((a, b)\) exists if and only if \(a\) and \(b\) are not both zero.
\(\textbf{Definition: }\) We say \(m\) is the least common multiple of \(a\) and \(b\) (written \(m = \text{lcm}(a, b)\)) if and only if
Note. \([0, 0]\) is not defined since there is no least common multiple of \(0\) and \(0\). \([a, b]\) exists if and only if \(a\) and \(b\) are not both zero.
\(\textbf{Proposition 1: }\) If \(a, b, c\in \mathbb{Z}^+\), \[ \text{lcm}(ca, cb) = c\text{lcm}(a, b). \]
\(textbf{Proof. }\)Let \(m = \text{lcm}(a, b)\). Then \(a\;|\;m\) and \(b\;|\;m\), which implies \[ ca\;|\;cm\qquad\text{and}\qquad cb\;|\;cm. \] Hence, \(cm\) is a common multiple of \(ca\) and \(cb\). According to the definition, we can get that \(cm\geq \text{lcm}(ca, cb)\). Suppose that \(m'\) is the least common multiple of \(ca\) and \(cb\), then \(ca\;|\;m'\) and \(cb\;|\;m'\). Thus, there exists \(k_1\) and \(k_2\) such that \[ m' = k_1ca\qquad\text{and}\qquad m' = k_2cb, \] which implies that \[ \frac{m'}{c} = k_1a\qquad\text{and}\qquad \frac{m'}{c} = k_2b. \] We can know that \(\frac{m'}{c}\) is a common multiple of \(a\) and \(b\). According to the definition, we can get that \(\frac{m'}{c}\geq m\), which means that \(m'\geq cm\). Hence, we can get that \(cm = m'\). \[ \tag*{$\square$} \]
\(\textbf{Proposition 2: }\) If \(a, b, c\in \mathbb{Z}^+\) and \(\gcd(a, b) = 1\), then \[ \text{lcm}(a, b) = ab. \]
\(\textbf{Proof. }\)Let \(m = \text{lcm}(a, b)\). Then \(a\;|\;m\) and \(b\;|\;m\), which implies \[ a\;|\;m\qquad\text{and}\qquad b\;|\;m. \] Since \(a\;|\;ab\) and \(b\;|\;ab\), we can get that \(ab\) is a common multiple of \(a\) and \(b\). According to the definition, we can get that \(ab\geq m\). On the other hand, since \(a\;|\;m\) and \(b\;|\;m\), there exists \(k_1\) and \(k_2\) such that \[ m = k_1a = k_2b. \]
\(\textbf{Theorem 1: }\) If \((a, b) = d\), then \((\frac{a}{d}, \frac{b}{d}) = 1\).
\(\textbf{Proof. }\)Suppose that \((a, b) = d\) and \(c= (\frac{a}{d}, \frac{b}{d})\), and our goal is to show that \(c= 1\).
\(\textit{Step 1. We show that \(c\geq 1\).}\)
We can get \(c\geq 1\) since \(c\) is the greatest common divisor of two integers and every greatest common divisor is greater than or equal to 1.
\(\textit{Step 2. We show that \(c\leq 1\).}\)
We use the facts that \(c\;|\;\frac{a}{d}\) and \(c\;|\;\frac{b}{d}\). We then know that there are integers \(q\) and \(r\) such that \(cq = \frac{a}{d}\) and \(cr = \frac{b}{d}\). That is, $$ (cd)q= a\text{ and }(cd)r = b. $$ Then we can get that \(cd\;|\;a\) and \(cd\;|\;b\), which implies that \(cd\) is a common divisor of \(a\) and \(b\). Since \(d\) is the greatest commond divisor of \(a\) and \(b\), we can get that \(cd\leq d\). Since \(d\) is positive, then we can get that \(c\leq 1\). Since we have \(c\leq 1\) and \(c\geq 1\), we can get \(c=1\).\[ \tag*{$\square$} \]
\(\textbf{Theorem 2 (The Division Algorithm). }\) Given positive integers \(a\) and \(b\), \(b\neq 0\), there exist unique integers \(q\) and \(r\), with \(0 \leq r < b\) such that $$ a= bq+r. $$
\(\textbf{Proof. }\)Consider the set of integers \(\{a,a-b,a-2b,a-3b, \dots \}\). Since \(a\geq 0\), it contains a subset of nonnegative integers which is nonempty and bounded below by 0. According to \(\textbf{Least-integer principle}\) \(\textbf{Least-integer principle. }\)A nonempty set of integers that is bounded below contains a smallest element. , it contains a smallest element. Let be \(r = a - qb\) be the smallest integer which is larger than or equal to 0.
\(\textit{Step 1. We show that \(r\) is less than \(b\)}\)
We will prove it with mathematical contradcition. Suppose that \(r\geq b\). Then we can get $$ r = a-qb\geq b, $$ $$ a-qb-b\geq 0, $$ $$ a-(q+1)b\geq 0. $$ Since \(0\leq a-(q+1)b \lt r\), \(r\) is not the smallest non-negative integer in the set. This contradicts the fact that \(r\) is the smallest non-negative integer in the set.
\(\textit{Step 2. We show that \(r\) and \(q\) are unique}\) (i.e. \((q, r)\) is an unique pair)
Suppose there is another pair \((q', r')\) such that $$ a= bq +r = bq'+r', $$ with \(0\leq r \lt b\) and \(0\leq r'\lt b\). Hence, we can get that $$ b(q-q') = r'-r. $$ Since \(q-q'\) is an integer and \(r'-r\) is an integer, we can get that \(b\) divides \(r'-r\) (i.e. \(b\;|\;(r'-r)\)). Since \(0\leq r \lt b\) and \(0\leq r'\lt b\), we can get $$ -b\lt -r\leq 0. $$ Thus, $$ -b\lt r'-r\lt b. $$ Since \(r'-r\) is a multiple of \(b\), the only multiple of \(b\) between \(-b\) and \(b\) is \(0\). Hence, we can get that \(r'-r=0\), which implies that \(r'=r\). Since we know that \(b(q-q') = r'-r\), we can get \(b(q-q') = 0\). Since \(b\neq 0\), we can get that \(q-q'=0\), which implies that \(q=q'\). \[ \tag*{$\square$} \]
\(\textbf{Theorem 2. The Division Algorithm (General).}\) Given integers \(a\) and \(b\), \(b\neq 0\), there exist integers \(q\) and \(r\), with \(0 \leq r \lt |b|\) such that $$ a= bq+r. $$
\(\textbf{Lemma 1 }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\).
\(\textbf{Proof. }\)Based on the definition, there are integers \(q_1, q_2, \dots, q_n\) such that \(a_1=dq_1,a_2=dq_2, \dots, a_n=dq_n\). Thus, $$ \begin{align*} c_1a_1+c_2a_2+\dots+c_na_n &= c_1dq_1+c_2dq_2+\dots+c_ndq_n\\ &= d(c_1q_1+c_2q_2+\dots+c_nq_n). \end{align*} $$ Thus, we can get that \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\). \[ \tag*{$\square$} \]
\(\textbf{Lemma 2. }\) If \(a=bq+r\), then \((a,b)=(b,r)\).
\(\textbf{Proof. }\)Let \(d= (a, b)\). Since \(a=bq+r\), we can write \(r = a+(-b)q\). Since \(d\;|\;a\), \(d\;|\;b\), and \(q\) is an integer, we can get \(d\;|\;r\) according to \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). . Thus, \(d\) is a common divisor of \(b\) and \(r\). Suppose that \(c\) is any common divisor of \(b\) and \(r\). Since \(c\;|\;b\) and \(c\;|\;r\), we can get \(c\;|\;a\) according to \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). . Thus, \(c\) is a common divisor of \(a\) and \(b\). Since \(d\) is the greatest common divisor of \(a\) and \(b\), we can get that \(c\leq d\) (i.e. any common divisor of \(b\) and \(r\) is less than or equal to \(d\)). Therefore, \(d=(b,r)\). \[ \tag*{$\square$} \]
\(\textbf{Theorem 3. Euclid's Algorithm. }\) If \(a\) and \(b\) are positive integers, \(b\neq 0\), and $$ a=bq+r,\qquad 0\leq r \lt b, $$ $$ b = rq_1+r_1, \qquad 0\leq r_1 \lt r, $$ $$ r =r_1q_2+r_2, \qquad 0\leq r_2 \lt r_1, $$ $$ r_1 = r_2q_3+r_3, \qquad 0\leq r_3 \lt r_2, $$ $$ \vdots $$ $$ r_k = r_{k+1}q_{k+2}+r_{k+2}, \qquad 0\leq r_{k+2} \lt r_{k+1}, $$ then for \(k\) large enough, say \(k=t\), we have $$ r_{t-1} = r_tq_{t+1}, $$ and \((a, b) = r_t\).
\(\textbf{Proof. }\)The sequence of nonnegative integers $$ b>r>r_1>r_2>\dots, $$ must come to an end. Eventually, one of the remainders will be zero. Suppose that it is \(r_{t+1}\). Then \(r_{t-1} = r_tq_{t+1}+r_{t+1}=r_tq_{t+1}\) and we can get \(r_t\;|\;r_{t-1}\). Thus, we can get \((r_{t-1},r_{t})=r_t\). We apply \(\textbf{Lemma 2}\) \(\textbf{Lemma 2. }\)If \(a=bq+r\), then \((a,b)=(b,r)\). . over and over, and can get $$ (a, b) = (b, r) = (r, r_1) = (r_1, r_2) = \dots =(r_{t-1}, r_t) =r_t. $$ If either \(a\) or \(b\) is negative, we can use the fact that \((a, b) = (-a, b)=(a,-b)=(-a, -b)\). \[ \tag*{$\square$} \]
\(\textbf{Corollary 1 (The Fundamental Lemma). }\) If \(a\) and \(b\) are positive integers, \(b\neq 0\), then there exist integers \(x\) and \(y\) such that $$ ax+by=(a, b). $$
\(\textbf{Proof. }\)Work the Euclidean Algorithm backward. The details are omitted. \[ \tag*{$\square$} \]
\(\textbf{Corollary 2. }\) If \(d\;|\;ab\) and \((d, a) = 1\), then \(d\;|\;b\).
\(\textbf{Proof. }\)Since \((d, a) = 1\), by \(\textbf{Corollary 1}\) \(\textbf{Corollary 1. }\)If \(a\) and \(b\) are positive integers, \(b\neq 0\), then there exist integers \(x\) and \(y\) such that $$ ax+by=(a, b). $$ , there exist integers \(x\) and \(y\) such that \(dx+ay=1\). Multiplying this by \(b\), we have $$ d(bx ) + (ab)y = b. $$ Since \(d\;|\;ab\) by assumption and \(d\;|\;db\), we can get \(d\;|\;aby\) and \(d\;|\;dbx\). Hence, we can get \(d\;|\;dbx+aby=b\).\[ \tag*{$\square$} \]
\(\textbf{Definition. }\) An integer \(p\in\mathbb{Z}^+\) is called prime if
\(\textbf{Lemma 3. }\) Every integer \(n, n > 1\), is divisible by a prime.
\(\textbf{Proof. }\)Consider the set of divisors of \(n\) which are greater than \(1\) and less than \(n\). It is either empty or nonempty. If it is empty, then \(n\) is prime by definition, and thus has a prime divisor, which is itself. If it is nonempty, then the least-integer principle says that it has a smallest element, call it \(d\). Now we have to show that \(d\) is a prime by contradcition. If \(d\) had a divisor greater than \(1\) and less than \(d\) (d is not a prime), then so would \(n\). However, this is impossible because \(d\) was the smallest such divisor. Thus \(d\) is prime. \[ \tag*{$\square$} \]
\(\textbf{Lemma 4. }\) Every integer \(n,n > 1\), can be written as a product of primes.
\(\textbf{Proof}\). From \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). , we know that there is a prime \(p_1\) such that \(p_1\;|\; n\). Hence there exists \(n_1\) where \(1\leq n_1< n\) such that \(n = p_1n_1\).If \(n_1= 1\), then we are done: \(n =p_1\) is an expression of n as a product of primes. If \(n_1 > 1\), then from \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). . again, there is a prime that divides \(n_1\). That is, \(n_1 = p_2n_2\), where \(p_2\) is a prime and \(1\leq n_2 \lt n_1\). If \(n_2 =1\), again we are done: \(n = p_1p_2\) is written as a product of primes. But if \(n_2 > 1\), then we apply \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). . once again and get that \(n_2 = p_3n_3'\) with \(p_3\) a prime and \(1\leq n_3 \lt n_2\). If \(n_3=1\), we are done. If not, we continue the same process. We will sooner or later come to \(n_i = 1\) since \(n > n_1 > n_2 >\dots\) and each \(n_i\) is positive; such a sequence cannot continue forever. For some \(k\), we will have \(n_k = 1\), in which case \(n = p_1p_2\cdots p_k\) is the desired expression of \(n\) as a product of primes. \[ \tag*{$\square$} \]
\(\textbf{Note.}\) each \(p_i\) may not be in unique.
\(\textbf{Theorem 4.(Euclid) }\)There are infinitely many primes.
\(\textbf{Proof}\). We will prove it with mathematical contradiction. Suppose there are finite primes \(p_1, p_2, \dots, p_r\). Consider the integer $$ n = p_1p_2\cdots p_r+1. $$ According to \(\textbf{Lemma 3}\) \(\textbf{Lemma 3. }\)Every integer \(n, n > 1\), is divisible by a prime. , we know that there is a prime \(p'\) such that \(p'\;|\;n\). Since there are finitly many primes, \(p'\) must be one of \(p_1, p_2, \dots, p_r\). Hence, we can get $$ p'\;|\;p_1p_2\cdots p_r+1\qquad\text{and}\qquad p'\;|\;p_1p_2\cdots p_r. $$ According to \(\textbf{Lemma 1}\) \(\textbf{Lemma 1. }\)If \(d\;|\;a_1, d\;|\;a_2, \dots, d\;|\;a_n\), then \(d\;|\;(c_1a_1+c_2a_2+\dots+c_na_n)\) for any integers \(c_1, c_2, \dots, c_n\). . , we can get $$ p'\;|\;(p_1p_2\cdots p_r+1)-(p_1p_2\cdots p_r)=1. $$ No primes divide \(1\) because all are greater than \(1\). Thus, contradiction exists. \[ \tag*{$\square$} \]
\(\textbf{Lemma 5. }\) If \(n\) is composite, then it has a divisor \(d\) such that \(1 \lt d \leq \sqrt{n} \).
\(\textbf{Proof}\). Suppose that \(n\) is composite. Then \(n = ab\) for some integers \(a\) and \(b\) with \(1 \lt a \lt n, 1 \lt b \lt n\). If \(a\) and \(b\) are both larger than \(\sqrt{n}\), then $$ n = ab > \sqrt{n}\sqrt{n} = n, $$ which is impossible. Thus, one of \(a\) and \(b\) must be less than or equal to \(n\). \[ \tag*{$\square$} \]
\(\textbf{Lemma 6. }\)If \(n\) is composite, then it has a prime divisor, \(p\), where \(p\leq \sqrt{n}\).
\(\textbf{Proof}\). Suppose that \(n\) is composite. Accroding to \(\textbf{Lemma 5}\) \(\textbf{Lemma 5. }\) If \(n\) is composite, then it has a divisor \(d\) such that \(1 \lt d \leq \sqrt{n} \). , , we can know that \(n\) has a divisor \(d\) such that \(1 \lt d \leq \sqrt{n} \). Accroding to \(\textbf{Lemma 4}\) \(\textbf{Lemma 4. }\)Every integer \(n,n > 1\), can be written as a product of primes. , , we can know that \(d\) has a prime divisor \(p\). Since \(p\;|\;d\), we can get \(p\;|\;n\) and \(p\leq d\leq \sqrt{n}\). \[ \tag*{$\square$} \]
\(\textbf{Lemma 7 (Euclid's Lemma). }\)If \(p\) is prime and \(p\;|\;ab\), then \(p\;|\;a\) or \(p\;|\;b\).
\(\textbf{Proof}\). Suppose that \(p\) is prime and \(p\;|\;ab\). Since \(p\) is prime, the only positive integer divisors of \(p\) are \(1\) and \(p\). Hence, \((p, a)=1\) or \((p, a)=p\). If \(p\;|\;a\) (i.e. \((p, a)=p\)), then we are done. If not, then \(p\) and \(a\) are relatively prime (i.e. \((p, a)=1\)). Accroding to \(\textbf{Corollary 2}\) \(\textbf{Corollary 2. }\)If \(d\;|\;ab\) and \((d, a) = 1\), then \(d\;|\;b\). , we can get \(p\;|\;b\). \[ \tag*{$\square$} \]
\(\textbf{Lemma 8. }\)If \(p\;|\;a_1a_2\cdots a_k\), then \(p\;|\;a_i\) for some \(i, i= 1, 2, \dots ,k\).
\(\textbf{Proof}\). We will prove it with mathematical induction. It is true by inspection if \(k = 1\), and \(\textbf{Lemma 7}\) \(\textbf{Lemma 7 (Euclid's Lemma). }\)If \(p\) is prime and \(p\;|\;ab\), then \(p\;|\;a\) or \(p\;|\;b\). shows that it is true if \(k = 2\) . Now, suppose that it is true for \(k=r\). Assume that \(p\;|\;a_1a_2\cdots a_{r+1}\), then \(p\;|\;(a_1a_2\cdots a_r)a_{r+1}\). According to \(\textbf{Lemma 7}\) \(\textbf{Lemma 7 (Euclid's Lemma). }\)If \(p\) is prime and \(p\;|\;ab\), then \(p\;|\;a\) or \(p\;|\;b\). , we can get \(p\;|\;a_1a_2\cdots a_r\) or \(p\;|\;a_{r+1}\). If \(p\;|\;a_1a_2\cdots a_r\), then \(p\;|\;a_i\) for some \(i, i= 1, 2, \dots ,r\). If \(p\;|\;a_{r+1}\), then it is still true that \(p\;|\;a_i\) for some \(i, i= 1, 2, \dots ,r+1\). \[ \tag*{$\square$} \]
\(\textbf{Lemma 9. }\)If \(q_1, q_2, \dots ,q_n\) are primes, and \(p\;|\; q_1q_2\cdots q_n\),then \(p = q_k\) for some \(k\).
\(\textbf{Proof. }\)According to \(\textbf{Lemma 8}\) \(\textbf{Lemma 8. }\)If \(p\;|\;a_1a_2\cdots a_k\), then \(p\;|\;a_i\) for some \(i, i= 1, 2, \dots ,k\). , we can know that \(p\;|\;q_k\) for some \(k\). Since \(q_k\) and \(p\) are both prime, we can get \(p = q_k\). \[ \tag*{$\square$} \]
\(\textbf{Theorem 5 (Fundamental Theorem of Arithmetic). }\)Every integer \(n, n > 1\), can be written as a product of primes in an unique way.
What do we mean "unique way"?
For an positive integer \(n\), we can write \(n\) as a product of primes in two ways: $$ n=p_1p_2\cdots p_m\quad\text{and}\quad n=q_1q_2\cdots q_r, $$ where \(p_1, p_2, \dots, p_m\) and \(q_1, q_2, \dots, q_r\) are primes. We need to show that \(m=r\) and \(p_1, p_2, \dots, p_m\) are just a rearrangement of the primes \(q_1, q_2, \dots, q_r\).
The Chain of Reasoning:
\(\textbf{Proof(1). }\)According to \(\textbf{Lemma 4}\) \(\textbf{Lemma 4. }\)Every integer \(n,n > 1\), can be written as a product of primes. , , that any integer \(n, n > 1\) can be written as a product of primes. Hence, we need to show that \(n\) cannot have two such representations of products of primes. Suppose that $$ n=p_1p_2\cdots p_m\quad\text{and}\quad n=q_1q_2\cdots q_r, $$ where \(p_1, p_2, \dots, p_m\) and \(q_1, q_2, \dots, q_r\) are primes. we have to show that the integers \(p_1, p_2, \dots, p_m\) are just a rearrangement of the integers \(q_1, q_2, \dots, q_r\). Since \(p_1\;|\; n\), we can know that $$ p_1\;|\;q_1q_2\cdots q_r. $$ According to \(\textbf{Lemma 9} \) \(\textbf{Lemma 9. }\)If \(q_1, q_2, \dots ,q_n\) are primes, and \(p\;|\; q_1q_2\cdots q_n\),then \(p = q_k\) for some \(k\). , we can get \(p_1 = q_k\) for some \(k\). Hence, we can rewrite \(n\) as $$ n=q_1q_2\cdots q_{k-1}q_k q_{k+1}\cdots q_r, $$ and $$ p_1p_2\cdots p_m=q_1q_2\cdots q_{k-1}q_k q_{k+1}\cdots q_r. $$ Since \(p_1=q_k\), we can get $$ p_2\cdots p_m=q_1q_2\cdots q_{k-1}q_{k+1}\cdots q_r. $$ We can repeat this process and get that \(p_2=q_{k_1}\), \(p_3=q_{k_2}\), \(\dots\), \(p_m=q_{k_{m-1}}\). We cannot run out of \(q\)'s before all the \(p's\) are gone, because there would be a product of primes equal to \(1\), which is impossible. Thus, we can get that \(m=r\) and \(p_1, p_2, \dots, p_m\) are just a rearrangement of the primes \(q_1, q_2, \dots, q_r\). \[ \tag*{$\square$} \]
\(\textbf{Proof(2). }\)Assume that \(n\) is the smallest positive integer and \(n\geq 2\) such that \(n\) can be written as a product of primes in two ways: $$ n=p_1p_2\cdots p_m\quad\text{and}\quad n=q_1q_2\cdots q_r, $$ where \(p_1, p_2, \dots, p_m\) and \(q_1, q_2, \dots, q_r\) are primes.
\(\textbf{Proof(2). }\)We will prove it with mathematical induction. It is true by inspection if \(n = 2\), and we assume that it is true for \(n = k\). We will show that it is true for \(n = k+1\). Suppose that $$ k+1 = p_1p_2\cdots p_m\quad\text{and}\quad k+1 = q_1q_2\cdots q_r, $$ where \(p_1, p_2, \dots, p_m\) and \(q_1, q_2, \dots, q_r\) are primes. Similar to \(\textbf{Proof(1)}\), we know that \(p_1=q_i\) for some \(i\leq r\). Hence, we can get $$ p_1p_2\cdots p_m=q_1q_2\cdots q_{i-1}q_i q_{i+1}\cdots q_r. $$ Thus, we know that $$ p_2\cdots p_m=q_1q_2\cdots q_{i-1}q_{i+1}\cdots q_r. $$ And we can know that \(p_2\cdots p_m=q_1q_2\cdots q_{i-1}q_{i+1}\cdots q_r\lt k+1\). By assumeption, we know that any integer less than \(k+1\) can be written as a product of primes in an unique way. Therefore, we show that \(k+1\) can be written as a product of primes in an unique way. \[ \tag*{$\square$} \]
Every nonzero and nonunit \(\alpha\in\mathbb{Z}[i]\) can be written as a product with at least one prime.
\(\textbf{Theorem. }\)Every nonzero, nonunit \(\alpha\in\mathbb{Z}[i]\) can be written as a product of primes. This factorization is unique up to the order of the factors and the multiplication of units.