跳转至

Chapter 1. Divisibility

Divisibility

  • Def 1.1 Divisibility: Let \(a, b \in \mathbb{Z}\), \(b \ne 0\), if \(\exists q \in \mathbb{Z}\) s.t.

    \[ a = qb \]

    Then we say that \(b\) devides \(a\) or \(a\) is divisible by \(b\), written as \(b\mid a\), and \(b\) is a divisor of \(a\), or \(a\) is a multiple of \(b\).

  • Thm 1.2 Properties of divisibility: Let \(a,b,c,d \in \mathbb{Z}\), then

    1. \(\forall c \in \mathbb{Z}, b\mid a \implies bc\mid ac\)
    2. \(c\mid b,~b\mid a \implies c \mid a\)
    3. \(a\mid b,~b\mid a \implies a=\pm b\)

    4. \(d\mid a,~d\mid b \implies \forall u,v \in \mathbb{Z},~d \mid (ua+vb)\)

      Proof

      Since \(d\mid a\) and \(d\mid b\), we have \(\exists x,y \in \mathbb{Z}\) s.t. \(a=dx\) and \(b=dy\), thus \(ua+vb=u(dx)+v(dy)=d(ux+vy)\), thus \(d\mid (ua+vb)\).

    5. (Cor) \(\forall u,v\in\mathbb{Z},~\gcd(a,b) \mid (ua+vb)\)

    6. Axiom 1.3 Well Ordering Principle (WOP): Let \(S \cap \mathbb{Z}^+ \ne \varnothing\), then
    7. There is a least positive integer in \(S\)
    8. There is a non-negative integer in \(S\)
    9. Thm 1.4 Long division: Let \(a,b \in \mathbb{Z}, b > 0\), then there exists a unique pair \((q,r)\in\mathbb{Z}^2\), \(0\le r<b\) s.t. \(a=qb+r\). We call \(q\) the quotient and \(r\) the remainder of \(a\) divided by \(b\).
    Proof
    • Uniqueness: Let \((q_1,r_1)\) and \((q_2,r_2)\) be two pairs satisfying the condition, then \(a=q_1 b + r_1 = q_2 b + r_2\), thus \((q_1-q_2) b = r_2 - r_1\). Since \(0\le r_1, r_2 < b\), we have \(-b < r_2 - r_1 < b\), thus \(q_1=q_2\) and \(r_1=r_2\).
    • Existence: Let \(S=\{a-xb: x\in\mathbb{Z}\}\), by WOP, there is a least non-negative integer \(r\) in \(S\), then \(\exists q \in \mathbb{Z}\) s.t. \(r=a-qb\). Suppose \(r\ge b\), then \(r-b=a-(q+1)b \in S\), and \(r-b\ge 0\), contradicting the definition of \(r\). Thus, \(0\le r < b\).

Greatest Common Divisor

  • Def 1.5 Greatest Common Divisor (GCD): Let \((a,b)\in\mathbb{Z}^2 \backslash \{(0,0)\}\), a GCD of \((a,b)\) is defined to be a positive integer \(d\) s.t.

    1. \(d\mid a,~d\mid b\)
    2. \(d'\mid a,~d'\mid b \implies d'\mid d\)

    Furthermore, we say \(a\) and \(b\) are co-prime if \(\gcd(a,b)=1\).

  • Thm 1.6: The GCD of \(a,b\) exists and is unique, denoted by \(\gcd(a,b)\).

    Proof
    • Uniqueness: Let \(d_1, d_2\) be two GCDs of \((a,b)\), then \(d_1\mid d_2\) and \(d_2\mid d_1\), by Thm 1.2(3), we have \(d_1=\pm d_2\). Since \(d_1, d_2 > 0\), we have \(d_1=d_2\).
    • Existence: Consider \(S=\{ua+vb: u,v\in\mathbb{Z}\}\), WLG, we assume \(b\ne 0\), then \(\pm b\in S\), \(S \cap \mathbb{Z}^+ \ne \varnothing\). By WOP, there is a least positive integer \(d\) in \(S\), then \(\exists u_0, v_0 \in \mathbb{Z}\) s.t. \(d=u_0a+v_0b\). We claim that \(d\) is a GCD of \((a,b)\).
      • \(d\mid a\): Let \(a=qd+r, 0\le r<d\), then \(r=a-qd=a-(qu_0a+qv_0b)=(1-qu_0)a+(-qv_0)b \in S\), this forces \(r=0\) due to minimality of \(d\), thus \(d\mid a\).
      • \(d\mid b\): Similar to \(d\mid a\).
      • Let \(d'\) be a common divisor of \(a,b\), then \(d'\mid (u_0a+v_0b)\), thus \(d'\mid d\).
      • Thus, \(d=\gcd(a,b)\).

  • Cor 1.7 Bézout's Identity: \(\forall (a,b)\in\mathbb{Z}^2\backslash \{(0,0)\}\), then \(\exists u,v \in \mathbb{Z}\) s.t. \(\gcd(a,b)=ua+vb\)

  • Thm 1.8 Properties of GCD: Let \(a,b,c,a_i\in\mathbb{Z}\), then

    1. \(m>0 \implies m\cdot \gcd(a,b)=\gcd(ma, mb)\)
    2. \(\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1\)
    3. \(\gcd(a_i,b)=1, i=1,2,\cdots,t \implies \gcd\left(\prod_{i=1}^t a_i, b\right)=1\)
    4. \(c\mid ab,~\gcd(c,b)=1 \implies c\mid a\)
    5. \(\forall r\in\mathbb{Z}, \gcd(a,b)=\gcd(a, b+ra)\)
    Proof
    1. Let \(d=\gcd(a,b), d'=\gcd(ma, mb)\),
      • \(d\mid a,~d\mid b\), thus \(md\mid ma, md\mid mb\), thus \(md \mid d'\)
      • \(d'\mid ma,~d'\mid mb\), thus \(\frac{d'}{m}\mid a, \frac{d'}{m}\mid b\), thus \(\frac{d'}{m} \mid d\), thus \(d' \mid md\)
      • Thus, \(md=d'\)
    2. Let \(d=\gcd(a,b)\), then \(\gcd(\frac{a}{d},\frac{b}{d})=\frac{1}{d}\gcd(a,b)=1\)
    3. Since Bézout's Identity, \(\exists u_i,v_i\in\mathbb{Z}\) s.t. \(u_i a_i+v_i b=1\), thus \(\prod_{i=1}^t(u_i a_i + v_i b) = 1 = \prod_{i=1}^t u_i a_i + b \sum_{i=1}^t v_i \prod_{j\ne i} u_j a_j\), thus \(\gcd(\prod_{i=1}^t a_i, b)=1\).
    4. Since \(c\mid ab\), \(\exists k\in\mathbb{Z}\) s.t. \(ab=kc\). Since \(\gcd(c,b)=1\), \(\exists u,v\in\mathbb{Z}\) s.t. \(uc+vb=1\), thus \(a=a(uc+vb)=uac+vab=uac+vkc=c(ua+vk)\), thus \(c\mid a\).
    5. Let \(d=\gcd(a,b), d'=\gcd(a, b+ra)\),
      • \(d\mid a,~d\mid b\), thus \(d\mid a, d\mid (b+ra)\), thus \(d\mid d'\)
      • \(d'\mid a,~d'\mid (b+ra)\), thus \(d'\mid a, d'\mid b\), thus \(d' \mid d\)
      • Thus, \(d=d'\)

Euclidean Algorithm

  • Thm 1.9 Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b\), we can compute \(r_2, r_3, \cdots\) by long division:

    \[ \begin{cases} r_0=q_1r_1+r_2, & 0\le r_2<r_1 \\ r_1=q_2r_2+r_3, & 0\le r_3<r_2 \\ \cdots \\ r_{i-1}=q_ir_i+r_{i+1}, & 0\le r_{i+1}<r_i \\ \cdots \\ r_{n-1}=q_{n}r_n, & r_{n+1}=0 \end{cases} \]

    then \(\gcd(r_{i-1},r_i)=\gcd(r_i, r_{i+1})\) for all \(i=1,2,\cdots,n-1\). In particular, \(\gcd(a,b)=\gcd(r_0,r_1)=\cdots=\gcd(r_{n-1},r_n)=r_n\)

    Info

    • the matrix form of Euclidean Algorithm:

      \[ \begin{pmatrix}a \\ b\end{pmatrix} =\begin{pmatrix}r_0 \\ r_1\end{pmatrix} =\begin{pmatrix}q_1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}r_1 \\ r_2\end{pmatrix} =\cdots =\begin{pmatrix}q_1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}q_2 & 1 \\ 1 & 0\end{pmatrix}\cdots\begin{pmatrix}q_n & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}r_n \\ 0\end{pmatrix} \]
    Proof

    By Thm 1.8(5), we have

    \[ \begin{aligned} \gcd(r_{i-1},r_i)&=\gcd(q_ir_i+r_{i+1}, r_i) \\ &=\gcd(r_{i+1}, r_i) \\ &=\gcd(r_i, r_{i+1}) \end{aligned} \]

  • Thm 1.10 Extended Euclidean Algorithm: Give \(a,b \in \mathbb{Z},b\ne 0\), let \(r_0=a, r_1=b, s_0=1, s_1=0, t_0=0, t_1=1\), we can compute \(r_2, r_3, \cdots\) by long division, and compute \(s_i,t_i\) by

    \[ \begin{cases} s_{i+1}=s_{i-1}-q_is_i \\ t_{i+1}=t_{i-1}-q_it_i \end{cases} \]

    then \(r_i=a s_i+b t_i\) for all \(i\ge 0\). In particular, \(\gcd(a,b)=r_n=a s_n+b t_n\).

    Info

    • the matrix form of Extended Euclidean Algorithm:

      \[ \begin{pmatrix}s_i & s_{i+1}\\ t_i & t_{i+1}\end{pmatrix}=\begin{pmatrix}s_{i-1} & s_i\\t_{i-1} & t_i\end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & -q_i\end{pmatrix},\quad \begin{pmatrix}s_0 & s_1\\t_0 & t_1\end{pmatrix}=\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix} \]
    Proof

    We can prove by induction that \(r_i=a s_i+b t_i\) for all \(i\ge 0\).

    • Base case:
      • \(i=0\), \(r_0=a s_0+b t_0=a\cdot 1 + b\cdot 0=a\)
      • \(i=1\), \(r_1=a s_1+b t_1=a\cdot 0 + b\cdot 1=b\)

    • Induction step: Assume \(r_i=a s_i+b t_i\) and \(r_{i-1}=a s_{i-1}+b t_{i-1}\), then

      \[ \begin{aligned} r_{i+1}&=r_{i-1}-q_i r_i \\ &=(a s_{i-1}+b t_{i-1})-q_i (a s_i+b t_i) \\ &=a (s_{i-1}-q_i s_i)+b (t_{i-1}-q_i t_i) \\ &=a s_{i+1}+b t_{i+1} \end{aligned} \]

Least Common Multiple

  • Def 1.11 Least Common Multiple (LCM): Let \(a,b\in\mathbb Z^*\), a LCM of \((a,b)\) is defined to be a positive integer \(D\) s.t.
    1. \(a\mid D,~b\mid D\)
    2. \(a\mid D',~b\mid D'\implies D\mid D'\)

  • Thm 1.12: The LCM of \(a,b\) exists and is unique, denoted by \(\mathrm{lcm}(a,b)\).

    Proof
    • Uniqueness: Let \(D_1, D_2\) be two LCMs of \((a,b)\), then \(D_1\mid D_2\) and \(D_2\mid D_1\), by Thm 1.2(3), we have \(D_1=\pm D_2\). Since \(D_1, D_2 > 0\), we have \(D_1=D_2\).
    • Existence: Consider \(S=\{x\in\mathbb{Z}^+: a\mid x, b\mid x\}\), since \(|ab|\in S\), \(S\ne \varnothing\). By WOP, there is a least positive integer \(D\) in \(S\), then \(\exists u_0, v_0 \in \mathbb{Z}\) s.t. \(D=u_0a=v_0b\). We claim that \(D\) is a LCM of \((a,b)\).
      • \(a\mid D\) and \(b\mid D\) is trivial.
      • Let \(D'\) be a common multiple of \(a,b\), then \(\exists q,r \in \mathbb{Z}\) s.t. \(D'=qD+r\) with \(0\le r<D\). Since \(a\mid D'\) and \(a\mid D\), we have \(a\mid r\), similarly, \(b\mid r\), thus \(r\in S\). This forces \(r=0\) due to minimality of \(D\), thus \(D\mid D'\).
      • Thus, \(D=\mathrm{lcm}(a,b)\).

  • Thm 1.13 Properties of LCM: Let \(a,b,c\in\mathbb{Z}^*\), then

    1. \(m>0 \implies m\cdot \mathrm{lcm}(a,b)=\mathrm{lcm}(ma, mb)\)
    2. \(\gcd(a,b)=1 \iff \mathrm{lcm}(a,b)=|ab|\)
      • \(\forall 1\leq i\neq j\leq t, \gcd(m_i,m_j)=1 \iff \mathrm{lcm}(m_1, m_2, \cdots, m_t) = \prod_{i=1}^t m_i\)
    3. \(\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|\)
    Proof
    1. Let \(D=\mathrm{lcm}(a,b), D'=\mathrm{lcm}(ma, mb)\),
      • \(a\mid D\) and \(b\mid D\), thus \(ma\mid mD\) and \(mb\mid mD\), thus \(D' \mid mD\)
      • \(ma\mid D'\) and \(mb\mid D'\), thus \(a\mid \frac{D'}{m}\) and \(b\mid \frac{D'}{m}\), thus \(D\mid \frac{D'}{m}\), thus \(mD \mid D'\)
      • Thus, \(mD=D'\)
    2. WLG, we assume \(a,b>0\). Let \(D=\mathrm{lcm}(a,b)\), prove the \(\implies\) direction as follows:
      • Because \(a\mid ab, b\mid ab\), we have \(D\mid ab\).
      • Since \(a\mid D\) and \(b\mid D\), thus \(\exists c\in \mathbb{Z}\) s.t. \(D=ac\), thus \(b\mid ac\), since \(\gcd(a,b)=1\), we have \(b\mid c\), thus \(\exists d\in\mathbb{Z}\) s.t. \(c=db\), thus \(D=ac=dab\), i.e. \(ab\mid D\).
      • Thus, \(D=|ab|\).
    3. WLG, we assume \(a,b>0\). Let \(d=\gcd(a,b)\), then \(\gcd(\frac{a}{d},\frac{b}{d})=1\) by Thm 1.8(2), thus \(\mathrm{lcm}(a,b) = d\cdot \mathrm{lcm}(\frac{a}{d},\frac{b}{d})=d\cdot \frac{a}{d}\cdot \frac{b}{d}=\frac{ab}{d}\), thus \(\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|\).

Prime

  • Def 1.14 Prime: A positive integer \(p>1\) is called prime if its only positive divisors are \(1\) and \(p\). Otherwise, we call it composite.

  • Thm 1.15 Equivalent definition of prime: \(p>1\) is a prime \(\iff\) \(\forall a,b\in \mathbb{Z}, p\mid ab \implies p\mid a\) or \(p\mid b\).

    Proof
    1. (\(\implies\))
      • Case 1: \(\gcd(p,b)=1\). Since \(p \mid ab\) and \(\gcd(p,b)=1\), by Thm 1.8(4), we have \(p\mid a\).
      • Case 2: \(\gcd(p,b)>1\). Let \(d=\gcd(p,b)\), so \(d\mid p\) and \(d\mid b\). Since \(p\) is a prime, \(d\) can only be \(1\) or \(p\), thus \(d=p\), thus \(p\mid b\).
    2. (\(\impliedby\)) Suppose \(p\) were not a prime, then \(\exists 1<u<p\) s.t. \(u\mid p\), thus \(p=\frac{p}{u}\cdot u \implies p\mid \frac{p}{u}\cdot u \implies p\mid \frac{p}{u}\) or \(p\mid u\), both of which are impossible since \(1<u<p\). Contradiction, thus \(p\) is a prime.

  • Thm 1.16: There are infinitely many primes.

    Proof by Euclid's method

    Suppose there are only finitely many primes \(p_1, p_2, \cdots, p_k\), consider \(n=\prod_{i=1}^k p_i + 1\) must be a composite number, then \(\exists p_i\) s.t. \(p_i\mid n\), thus \(p_i\mid (n-\prod_{i=1}^k p_i)\implies p_i\mid 1\), contradiction, thus there are infinitely many primes.

    Proof by Saliak's method

    Chose \(n>1\), then \(\gcd(n, n+1)=1\). Let \(p_1, p_2\) be a prime divisor of \(n\) and \(n+1\) respectively, then \(p_1\ne p_2\), thus \(n(n+1)\) has at least two distinct prime divisors. Then consider \(n(n+1)(n(n+1)+1)\), it has at least three distinct prime divisors. By induction, we can show that there are infinitely many primes.

  • Thm 1.17 Fundamental Theorem of Arithmetic: Any positive integer \(n>1\) can be uniquely factorized into a product of primes with \(p_1\le p_2 \le \cdots \le p_m\)

    \[ n=p_1\cdot p_2 \cdots p_m \]

    • Notation: Let \(p\in \mathbb{P}\), \(n\in \mathbb{Z}^+\), \(v_p(n)\) denotes the largest non-negative integer \(k\) s.t. \(p^k\mid n\). Then Thm 1.17 can be restated as

      \[ n=\prod_{p\in \mathbb{P}} p^{v_p(n)} \]
    Proof
    • Existence: By induction on \(n\).
      • Base case: \(n=2\), obviously true.
      • Induction step: \(n>2\), if \(\frac{n}{p_1} = 1\) for some prime divisor \(p_1\), then \(n=p_1\) is a product of primes. Otherwise, \(\frac{n}{p_1}\in \mathbb{Z}\) and \(1<\frac{n}{p_1}<n\). By induction hypothesis, \(\frac{n}{p_1}\) can be factorized into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) can be factorized into a product of primes.
    • Uniqueness: By induction on \(n\).
      • Base case: \(n=2\), obviously true.
      • Induction step: \(n>2\), let \(p_1\) be the smallest prime divisor of \(n\), then \(\frac{n}{p_1}\in \mathbb{Z}\) and \(1\leq\frac{n}{p_1}<n\). By induction hypothesis, \(\frac{n}{p_1}\) has a unique factorization into a product of primes, thus \(n=p_1\cdot \frac{n}{p_1}\) has a unique factorization into a product of primes.

  • Cor 1.18: Let \(m,n\in \mathbb{Z}^+\), then

    1. \[ \gcd(m,n)=\prod_{p\in \mathbb{P}} p^{\min\{v_p(m), v_p(n)\}} \]
    2. \[ \mathrm{lcm}(m,n)=\prod_{p\in \mathbb{P}} p^{\max\{v_p(m), v_p(n)\}} \]

  • Thm 1.19: There are infinitely many primes of the form \(4n+3\).

    Proof

    • Suppose there are only finitely many primes of the form \(4n+3\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the other primes must be of the form \(4n+1\) or \(2\). Consider the number:

      \[ N = 4\prod_{i=1}^k p_i - 1 \]

      then we have \(N \equiv 3 \pmod{4}\). Since \(N\) is of the form \(4n+3\), it must be a composite number.

    • Since \(N\) is odd, \(2\nmid N\), suppose \(N\) is a composite number. Thus, any prime divisor of \(N\) must be of the form \(4n+1\) or \(4n+3\).

      • If all prime divisors of \(N\) are of the form \(4n+1\), then \(N \equiv 1 \pmod{4}\) since \(\prod_{i=1}^t (4n_i+1) \equiv 1 \pmod{4}\), contradiction.
      • Thus, \(\exists i\in \{1,2,\dots,k\}\) s.t. \(p_i\mid N\), thus \(p_i\mid (4\prod_{i=1}^k p_i - N)\), thus \(p_i\mid 1\), contradiction.
    • Thus, \(N\) is a new prime of the form \(4n+3\), contradiction. Thus, there are infinitely many primes of the form \(4n+3\).

  • Thm 1.20: There are infinitely many primes of the form \(3n+2\).

    Proof

    • Suppose there are only finitely many primes of the form \(3n+2\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Then the other primes must be of the form \(3n+1\) or \(3\). Consider the number:

      \[ N = 3\prod_{i=1}^k p_i - 1 \]

      then we have \(N \equiv 2 \pmod{3}\). Since \(N\) is of the form \(3n+2\), it must be a composite number.

    • Since \(3\nmid N\), thus any prime divisor of \(N\) must be of the form \(3n+1\) or \(3n+2\).

      • If all prime divisors of \(N\) are of the form \(3n+1\), then \(N \equiv 1 \pmod{3}\) since \(\prod_{i=1}^t (3n_i+1) \equiv 1 \pmod{3}\), contradiction.
      • Thus, \(\exists i\in \{1,2,\dots,k\}\) s.t. \(p_i\mid N\), thus \(p_i\mid (3\prod_{i=1}^k p_i - N)\), thus \(p_i\mid 1\), contradiction.
    • Thus, \(N\) is a new prime of the form \(3n+2\), contradiction. Thus, there are infinitely many primes of the form \(3n+2\).

  • Thm 1.21: There are infinitely many primes of the form \(4n+1\).

    Proof By Quadratic Residue

    • Suppose there are only finitely many primes of the form \(4n+1\), denoted by \(\{p_1, p_2, \dots, p_k\}\). Consider the number:

      \[ N = \left(2\prod_{i=1}^k p_i\right)^2 + 1 = 4\left(\prod_{i=1}^k p_i\right)^2 + 1 \]

      then we have \(N \equiv 1 \pmod{4}\). Since \(N\) is of the form \(4n+1\), it must be a composite number.

    • Let \(p\) be a prime divisor of \(N\), obviously \(p\ne 2\) since \(N\) is odd and \(p\neq p_i\) since \(p_i\nmid N\). Thus, we have

      \[ \left(2\prod_{i=1}^k p_i\right)^2 \equiv -1 \pmod{p} \]

      which means \(-1\) is a quadratic residue modulo \(p\)

    • Thus \(\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=1\), thus \(p\equiv 1 \pmod{4}\), thus \(p\) is a new prime of the form \(4n+1\), contradiction. Thus, there are infinitely many primes of the form \(4n+1\).