Before we introduce Integers, we have to know what natural numbers are. In order to build the natural number, we need to introduce two concept:
We use \(\mathbb{N}\) to denote the collection of all natural numbers. In that case, \(\mathbb{N}\) is defined as a collection of \(0\) and everything which can be obtained from 0 by incrementing: \[ \mathbb{N}=\{0, 0++, (0++)++, \cdots\}. \]
\(\textbf{Definition: }\) \[ \mathbb{Z}=\{\cdots,-2,-1,0,1,2,\cdots\}. \]
\(\textbf{Definition: }\)Any set that satisfies all following axioms is called a field.
\(\textbf{Proposition 1. }\)The additive identity is unique.
\(\textbf{Proof: }\)Suppose \(0\) and \(0'\) are both additive identities. Then \[ 0+0'=0'+0=0. \] Since \(0'\) is an additive identity, we have \[ 0+0'=0. \] Since \(0\) is an additive identity, we have \[ 0+0'=0'. \] Therefore, \(0=0'\). \[ \tag*{$\square$} \]
\(\textbf{Proposition 2. }\)The additive inverse of an integer \(a\) is unique.
\(\textbf{Proof: }\)Suppose \(b\) and \(c\) are both additive inverses of \(a\). Then \[ a+b=b+a=0 \] and \[ a+c=c+a=0. \] Hence, we can get \[ a+b=a+c. \] Since \(b\) is an additive inverse of \(a\), we have \[ a+b+b = 0+ b = a+c+b = a + b + c = 0 + c. \] Therefore, we can get \[ b = c. \] \[ \tag*{$\square$} \]
\(\textbf{Theorem 1. }\)For all integers \(a\), \[ a0=0a=0. \]
\(\textbf{Proof: }\)Since \(0\) is an additive identity, we have \[ a0=a(0+0)=a0+a0. \] Since \(a0\) has an additive inverse and we call it \(b\), we have \[ a0+b = a0+a0+b, \] \[ 0 = a0+0 = a0. \] \[ \tag*{$\square$} \]
\(\textbf{Proposition 3. }\)For all integers \(a\), \[ (-1)a=-a. \]
\(\textbf{Proof: }\)Since \(a\) has an additive inverse and we call it \(b\), we have \[ a+b=0. \] Since \(0\) is an additive identity, we have \[ (-1)a+1a=(-1)a+1a+0=(-1)a+1a+(-a)+a=(-1)a+(-a)+a+1a=0+1a=1a. \] Therefore, we can get \[ (-1)a=-a. \] \[ \tag*{$\square$} \]
\(\textbf{Definition: }\)There is a nonempty set \(\mathbb{Z}^+\subset \mathbb{Z}\) of integers called the set of positive integers such that
\(\textbf{Definition: }\)For integers \(a\) and \(b\), we say that \(a\) is less than \(b\) and write \(a\lt b\) if \(b-a\) is a positive integer \((b-a\in\mathbb{Z}^+)\).
\(\textbf{Proposition 4. }\)For all integers \(a\) and \(b\), if \(ab=0\), then \(a=0\) or \(b=0\).
\(\textbf{Proof. }\)I will prove it with mathematical contradiction. Suppose that there exists integers \(a\) and \(b\) such that \(ab=0\) and \(a\neq 0\) and \(b\neq 0\).
\(\textbf{Case 1. }\)If \(a\in\mathbb{Z}^+\) and \(b\in\mathbb{Z}^+\), then \(ab\in\mathbb{Z}^+\). Since \(0\notin \mathbb{Z}^+\), it is a contradiction.
\(\textbf{Case 2. }\)Without loss of generality, we can assume that \(a\in\mathbb{Z}^+\) and \(b\in\mathbb{Z}^-\). Then \(-b\in\mathbb{Z}^+\) for \(b\neq 0\). Then we can get \[ a(-b) = -ab = -0 = 0\in\mathbb{Z}^+, \] because of the Closure of Multiplication in \(\mathbb{Z}^+\). It is a contradiction.
\(\textbf{Case 3. }\)We assume that \(a, b\in\mathbb{Z}^-\). Then we can know that \(-a\in\mathbb{Z}^+\) and \(-b\in\mathbb{Z}^+\) for both \(a\neq 0\) and \(b\neq 0\). Then we can get \[ (-a)(-b) = ab = 0\in\mathbb{Z}^+, \] because of the Closure of Multiplication in \(\mathbb{Z}^+\). It is a contradiction. \[ \tag*{$\square$} \]
\(\textbf{Definition: }\)For a positive integer \(n\in\mathbb{Z}^+\), we define the set \(\mathbb{Z}/n\mathbb{Z}\) as \[ \mathbb{Z}/n\mathbb{Z}=\{0,1,2,\cdots,n-1\}. \] For \(a,b\in\mathbb{Z}/n\mathbb{Z}\), we define addition and multiplication as follows: \[ a+b=(a+b)\mod n, \] \[ ab=(ab)\mod n. \]
\( \textbf{Example: }\)Let \(n=5\). Then \[ \mathbb{Z}/n\mathbb{Z}=\mathbb{Z}/5\mathbb{Z}=\{0,1,2,3,4\}. \]
\(\textbf{Note: }\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}/(-n)\mathbb{Z}\)
\(\textbf{Definition: }\)Every nonempty subset of \(\mathbb{Z}^+\) has a least element. That is, if \(S\subset\mathbb{Z}^+\) and \(S\neq\emptyset\), then there exists an integer \(l\in S\) such that \[ l\leq s\;\text{for all}\;s\in S. \]
\(\textbf{Proposition 5. }\)\(1\) is the least element of \(\mathbb{Z}^+\).
\(\textbf{Proof: }\)We will prove it with mathematical contradiction. Let \(S=\mathbb{Z}^+\) and we can know that \(S\neq\emptyset\). According to the well-ordering principle, there exists an integer \(l\in S\) such that \[ l\leq s\;\text{for all}\;s\in S. \] It means that \[ l\leq 1. \] Since \(l\in\mathbb{Z}^+\), we have \[ l\cdot l\leq l\cdot 1 = l. \] Thus, we can get \((l\cdot l)\) is the smallest element of \(\mathbb{Z}^+\). The contradcition exists. Therefore, \(1\) is the least element of \(\mathbb{Z}^+\).
\(\textbf{Proposition 6. }\)For \(a, b\in\mathbb{Z}^+\), if \(a\mid b\), then \(a\leq b\).
\(\textbf{Proof: }\)Suppose \(a\mid b\) where \(a, b\in\mathbb{Z}^+\). Then there exists an integer \(k\) such that \[ ak=b. \] First, we have to show that \(k\in\mathbb{Z}^+\) by contradiction. Suppose that \(k\in\mathbb{Z}^-\cup \{0\}\). If \(k = 0\), then \[ ak = 0 \neq b, \] since \(b\in\mathbb{Z}^+\). If \(k\in\mathbb{Z}^-\), then \(-k\in\mathbb{Z}^+\). \[ a\cdot(-k) = -ak = -b\in\mathbb{Z}^+, \] because of the Closure of Multiplication in \(\mathbb{Z}^+\). According to \(\textbf{Trichotomy Law}\) \(\textbf{Trichotomy Law. }\)For every integer \(a\), exactly one of the following statement is true: \[ a\in\mathbb{Z}^+, \] \[ a=0, \] \[ -a\in\mathbb{Z}^+. \] , we can know that if \(-b\in\mathbb{Z}^+\), then \(b\notin\mathbb{Z}^+\), which is a contradiction. Thus, we can know that \(k\in\mathbb{Z}^+\). According to \(\textbf{Proposition 5}\) \(\textbf{Proposition 5. }\)\(1\) is the least element of \(\mathbb{Z}^+\). , we can get that \(k\geq 1\). If \(k=1\), then \[ a\cdot 1 = a = b. \] If \(k\gt 1\), then \[ k - 1\in\mathbb{Z}^+. \] And we can get \[ a(k-1) = ak-a = b-a\in\mathbb{Z}^+, \] because of the Closure of Multiplication in \(\mathbb{Z}^+\). Hence, \(a\lt b\). Therefore, we can get \(a\leq b\). \[ \tag*{$\square$} \]
\(\textbf{Definition. }\)An integer \(a\) is called even if there exists an integer \(b\) such that \[ a=2b. \] (i.e. \(a\) is divisible by \(2\).)
\(\textbf{Definition. }\)An integer \(a\) is called odd if there exists an integer \(b\) such that \[ a=2b+1. \]
\(\textbf{Proposition 5. }\)Every \(n\in\mathbb{Z}\) is even or odd.
\(\textbf{Proof. }\)We will prove it with two steps.
\(\textbf{Step 1. }\)Every integer \(n\in\mathbb{Z}^+\) is even or odd.
We will prove it with mathematical contradiction. Let \(S=\{n\in\mathbb{Z}^+|n\;\text{is neither even nor odd}\}\) and suppose that \(S\) is not empty. According to \(\textbf{Well-ordering Principle}\) \(\textbf{Well-ordering Principle. }\)Every nonempty subset of \(\mathbb{Z}^+\) has a least element. That is, if \(S\subset\mathbb{Z}^+\) and \(S\neq\emptyset\), then there exists an integer \(l\in S\) such that \[ l\leq s\;\text{for all}\;s\in S. \] , we can know that \(S\) has a least element \(l\). Since \(1 = 2\cdot 0 +1\), we can know that \(1\) is odd. In that case, we can get that \(1\notin S\). According to \(\textbf{Proposition_5. }\)\(1\) is the least element of \(\mathbb{Z}^+\). , we can know that \(l\gt 1\) since \(1\notin S\). Thus, we can get \(l-1\in\mathbb{Z}^+\) for \(l-1\lt l\). Then we can get that \(l-1\) is even or odd. If \(l-1\) is even, then there exists an integer \(t\) such that \[ l-1=2t. \] Then we can get \[ l=2t+1, \] which means that \(l\) is odd. It is a contradiction. If \(l-1\) is odd, then there exists an integer \(t\) such that \[ l-1=2t+1. \] Then we can get \[ l=2t+2=2(t+1), \] which means that \(l\) is even. It is a contradiction. Therefore, we can get that every integer \(n\in\mathbb{Z}^+\) is even or odd.
\(\textbf{Step 2. }\)There is no integer \(n\in\mathbb{Z}^+\) such that \(n\) is both even and odd.
I will prove it with mathematical contradiction. Suppose that there exists an integer \(n\in\mathbb{Z}^+\) such that \(n\) is both even and odd. Then there exists an integer \(k, l\) such that \[ n=2k=2l+1. \] Then we can get \[ 2k-2l=1, \] \[ 2(k-l)=1. \] Since \(k-l\in\mathbb{Z}\), we can get \(2\mid 1\). According to \(\textbf{Proposition 6}\) \(\textbf{Proposition 6. }\)For \(a, b\in\mathbb{Z}^+\), if \(a\mid b\), then \(a\leq b\). , we can know that \(2\leq 1\). It is a contradiction. Thus, we can get that there is no integer \(n\in\mathbb{Z}^+\) such that \(n\) is both even and odd. Therefore, we can get that every integer \(n\in\mathbb{Z}\) is either even or odd. \[ \tag*{$\square$} \]
\(\textbf{Theorem. }\)Let \(P\) is a property of \(\mathbb{Z}^+\) such that:
\(\mathbb{Proof. }\)Suppose \(P\) is a property of \(\mathbb{Z}^+\) such that:
\(\textbf{Definition. }\)The Farey sequence of order \(n\) is the sequence of completely reduced fractions between \(0\) and \(1\) which, when in lowest terms, have denominators less than or equal to \(n\), arranged in order of increasing size.
\(\textbf{Note. }\)The Farey sequence of order \(n\) is denoted by \(\mathfrak{F}_n\).
\(\textbf{Example. }\)The Farey sequence of order \(5\) is \[ \mathfrak{F}_5 = \{\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}\}. \]
\(\textbf{Note. }\)If \(a/b\) and \(c/d\) are two consecutive terms in some Farey sequence \(\mathfrak{F}_n\), then they remain consecutive until \(\mathfrak{F}_{b+d}\), at which point \(\frac{a+c}{b+d}\) is the unique fraction between them.
\(\textbf{Note. }\)If \(a/b\) and \(c/d\) are two consecutive terms in some Farey sequence \(\mathfrak{F}_n\) where \(a/b\lt c/d\), then \[ \frac{c}{d}-\frac{a}{b}=\frac{1}{bd}. \] and \[ \frac{a}{b}\lt\frac{a+c}{b+d}\lt\frac{c}{d}. \]
\(\textbf{Goal. }\)We want to have the situation that if \(a/b\) and \(c/d\) are two consecutive terms in some Farey sequence \(\mathfrak{F}_n\) where \(a/b\lt c/d\) and \(p/q\) is between them. We want to get \(q\geq b+d\) and if \(q=b+d\), then \(p=a+c\).
\(\textbf{Definition. }\)The extended Farey sequence of order \(n\) is the sequence of completely reduced fractions without restriction of \([0,1]\).
\(\textbf{Definition. }\)A Gaussian integer is a complex number of the form \(a+bi\) where \(a\) and \(b\) are integers. We denote it as \(\mathbb{Z}[i]=\{a+bi: a, b\in\mathbb{Z}\}\).
\(\textbf{Note. }\)The set of Gaussian integers is a just a pair of integers such as \[ \mathbb{Z}[i]=\{(a, b)\;|\;a, b\in\mathbb{Z}\}. \]
We have to define addition and multiplication of Gaussian integers. \[ (a, b) + (c, d) = (a+c, b+d), \] \[ (a, b) \cdot (c, d) = (ac-bd, ad+bc). \]
\(\textbf{Definition. }\)Let \(a\) and \(b\) be in \(\mathbb{Z}[i]\). We say that \(a\) divides \(b\) (\(a\;|\b\)) if there exists a Gaussian integer \(c\) such that \[ ac = b. \]
\(\textbf{Definition. }\)Let \(\alpha = a + bi\) be in \(\mathbb{Z}[i]\). The conjugate of \(\alpha = a + bi\) is denoted by \(\overline{a}\) and defined by \[ \overline{a} = a - bi. \]
\(\textbf{Note. }\) \[ \overline{\alpha+\beta} = \overline{\alpha} + \overline{\beta}, \] \[ \overline{\alpha\beta} = \overline{\alpha}\overline{\beta} \]
\(\textbf{Definition. }\)Let \(\alpha = a + bi\) be in \(\mathbb{Z}[i]\). The norm of \(\alpha = a + bi\) is denoted by \(N(\alpha)\) and defined by \[ N(\alpha) = \alpha\overline{\alpha} = (a + bi)(a - bi) = a^2 + b^2. \]
\(\textbf{Proposition 7. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]\). Then \(N(\alpha\beta) = N(\alpha)N(\beta)\).
\(\textbf{Proof. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]\). Then \[ N(\alpha\beta) = (\alpha\beta)(\overline{\alpha\beta}) = (\alpha\beta)(\overline{\alpha}\overline{\beta}) = (\alpha\overline{\alpha})(\beta\overline{\beta}) = N(\alpha)N(\beta). \] \[ \tag*{$\square$} \]
\(\textbf{Proposition 8. }\)There are only 4 units in \(\mathbb{Z}[i]\), which are \[ \pm 1, \pm i. \]
\(\textbf{Proof. }\)Suppose that \(\alpha\) is a unit in \(\mathbb{Z}[i]\). Then there exists a Gaussian integer \(\beta\) such that \[ \alpha\beta = 1. \] Then \[ N(\alpha\beta) = N(1) = 1. \] By \(\textbf{Proposition 7. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]\). Then \(N(\alpha\beta) = N(\alpha)N(\beta)\). , \[ N(\alpha)N(\beta) = 1. \] Since \(N(\alpha)\) and \(N(\beta)\) are non-negative integers, we have \(N(\alpha) = N(\beta) = 1\). \[ \tag*{$\square$} \]
\(\textbf{Definition. }\) Let \(\pi\) be a Gaussian integer. We say that \(\pi\) is a Gaussian prime
\(\textbf{Claim. }\)\(1+i\) is a guassian prime.
\(\textbf{Proof. }\)Since \(1+i\) is not a unit, we have to prove that if \(1+i=\alpha\beta\) for some \(\alpha, \beta\in\mathbb{Z}[i]\), then \(\alpha\) is a unit or \(\beta\) is a unit. Suppose that \(1+i=\alpha\beta\) for some \(\alpha, \beta\in\mathbb{Z}[i]\). Then \[ N(1+i) = N(\alpha\beta) = N(\alpha)N(\beta). \] Since \(N(1+i) = 2\) and norms are non-negative, we have \(N(\alpha) = 1\) or \(N(\beta) = 1\).
\(\textbf{Proposition 9. }\)If \(N(\pi)\) is a prime number in \(\mathbb{Z}\), then \(\pi\) is a Gaussian prime.
\(\textbf{Proof. }\)Suppose that \(\pi\) is a Gaussian prime. Then \(\pi\) is not a unit.
\(\textbf{Definition. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]_\mu\). We say that \(\alpha\) is congruent to \(\beta\) modulo \(\mu\) and write \(\alpha\equiv\beta\mod \mu\) if \(\mu\;|\;(\alpha-\beta)\).
\(\textbf{Theorem. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]\) with \(\beta\neq 0\). Then there exist Gaussian integers \(\gamma\) and \(\rho\) such that \[ \alpha = \beta\gamma + \rho \] where \(N(\rho) \leq \frac{1}{2} N(\beta)\).
\(\textbf{Proof. }\)We have \(\alpha, \beta \in \mathbb{Z}[i]\) with \(\beta \neq 0\) and we want to construct \(\gamma, \rho \in \mathbb{Z}[i]\) such that \(\alpha = \beta\gamma + \rho\) where \(N(\rho) \leq \frac{1}{2} N(\beta)\).
Write \[ \frac{\alpha}{\beta} = \frac{\alpha\overline{\beta}}{\beta\overline{\beta}} = \frac{\alpha\overline{\beta}}{N(\beta)} = \frac{m + ni}{N(\beta)}, \] where we set \(\alpha\overline{\beta} = m + ni\). Divide \(m\) and \(n\) by \(N(\beta)\) using the division algorithm in \(\mathbb{Z}\): \[ m = N(\beta)q_1 + r_1, n = N(\beta)q_2 + r_2, \] where \(q_1\) and \(q_2\) are in \(\mathbb{Z}\) and \(0 \leq |r_1|, |r_2| \leq \frac{1}{2} N(\beta)\). Then \[ \frac{\alpha}{\beta} = \frac{N(\beta)q_1 + r_1 + (N(\beta)q_2 + r_2)i}{N(\beta)} = q_1 + q_2i + \frac{r_1 + r_2i}{N(\beta)}. \] In that case, we can get the following: \[ \alpha = \beta(q_1 + q_2i) + \frac{\beta(r_1 + r_2i)}{N(\beta)}=\beta(q_1 + q_2i) + \frac{\beta(r_1 + r_2i)}{\beta\overline{\beta}}. \] After a little algebra, we can get \[ \alpha = \beta(q_1 + q_2i) + \frac{r_1 + r_2i}{\overline{\beta}}. \]
Let \(\gamma = q_1 + q_2i\) (this will be our desired quotient), so after a little algebra the above equation becomes \[ \alpha - \beta\gamma = \frac{r_1 + r_2i}{\overline{\beta}}. \] We will show \(N(\alpha - \beta\gamma) \leq \frac{1}{2} N(\beta)\), so using \(\rho = \alpha - \beta\gamma\) will settle the division theorem. Take norms of both sides of \(\alpha - \beta\gamma = \frac{r_1 + r_2i}{\overline{\beta}}\), where on the right side we use the norm on complex numbers and its multiplicativity (Remark 1.3). Letting \(z = \frac{r_1 + r_2i}{\overline{\beta}}\), so \[ z\overline{\beta} = r_1 + r_2i, \] and \[ N(z) N(\overline{\beta}) = N(r_1 + r_2i) = r_1^2 + r_2^2. \] Since \(N(\beta) = N(\overline{\beta})\), \[ N(z) = N(\alpha - \beta\gamma) = \frac{r_1^2 + r_2^2}{N(\beta)}. \] Since we know that \(0 \leq |r_1|, |r_2| \leq \frac{1}{2} N(\beta)\) by using the divison algorithm in \(\mathbb{Z}\), we have \(N(\alpha - \beta\gamma) \leq \frac{(\frac{1}{4} N(\beta))^2 + (\frac{1}{4} N(\beta))^2}{N(\beta)} = \frac{1}{2} N(\beta)\). \[ \tag*{$\square$} \]
\(\textbf{Corollary. }\)Let \(\alpha\) and \(\beta\) be in \(\mathbb{Z}[i]\) with \(\beta\neq 0\). Then there exist Gaussian integers \(\gamma\) and \(\rho\) such that \[ \alpha = \beta\gamma + \rho \] where \(N(\rho) \leq N(\beta)\).