Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

8.S: Topics in Number Theory (Summary)

  • Page ID
    7084
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Important Definitions

    • Greatest common divisor of two integers, page 414
    • Linear combination of two integers, page 423
    • Prime number, page 426
    • Composite number, page 426
    • Prime factorization, page 427
    • Relatively prime integers, page 428
    • Diophantine equation, page 441
    • Linear Diophantine equation in two variables, page 441

    Important Theorems and Results about Relations, Equivalence Relations, and Equivalence Classes

    • Theorem 8.3. Let \(a\) and \(b\) be integers with \(a \ne 0\) and \(b > 0\). Then gcd(\(a, b\)) is the only natural number \(d\) such that

      (a) \(d\) divides \(a\),
      (b) \(d\) divides \(b\), and
      (c) if \(k\) is an integer that divides both \(a\) and \(b\), then \(k\) divides \(d\).
    • Theorem 8.8. Let \(a\) and \(b\) be integers, not both 0. Then gcd(\(a, b\)) can be written as a linear combination of \(a\) and \(b\). That is, there exist integers \(u\) and \(v\) such that gcd(\(a, b\)) \(= au + bv\).

    • Theorem 8.9.

      1. The greatest common divisor, \(d\), is a linear combination of \(a\) and \(b\). That is, there exist integers \(m\) and \(n\) such that \(d = am + bn\).

      2. The greatest common divisor, \(d\), divides every linear combination of \(a\) and \(b\). That is, for all \(x, y \in \mathbb{Z}\), \(d\ |\ (ax + by)\).

      3. The greatest common divisor, \(d\), is the smallest positive number that is a linear combination of \(a\) and \(b\).

    • Theorem 8.11. Let \(a\) and \(b\) be nonzero integers, and let \(p\) be a prime number.

      1. If \(a\) and \(b\) are relatively prime, then there exist integers m and n such that \(am + bn = 1\). That is, 1 can be written as linear combination of \(a\) and \(b\).

      2. If \(p\ |\ a\),then \(\text{gcd}(a, p) = p\).

      3. If \(p\) does not divide \(a\), then \(\text{gcd}(a, p) = 1\).

    • Theorem 8.12 Let \(a\), \(b\), and \(c\) be integers. If a and b are relatively prime and \(a\ |\ (bc)\), then \(a\ |\ c\).

    • Corollary8.14

      1. Let \(a, b \in \mathbb{Z}\), and let \(p\) be a prime number. If \(p\ |\ (ab)\), then \(p\ |\ a\) or \(p\ |\ b\).

      2. Let \(p\) be a prime number, let \(n \in \mathbb{N}\), and let \(a_1, a_2, ..., a_n \in \mathbb{Z}\). If \(p\ |\ (a_{1}a_{2} \cdot\cdot\cdot a_{n})\), then there exists a natural number \(k\) with \(1 \le k \le n\) such that \(p\ |\ a_k\).

    • Theorem 8.15, The Fundamental Theorem of Arithmetic

      1. Each natural number greater than 1 is either a prime number or is a product of prime numbers.

      2. Let \(n \in \mathbb{N}\) with \(n > 1\). Assume that
        \[n = p_{1}p_{2} \cdot\cdot\cdot p_{r} \text{ and that } n = q_{1}q_{2} \cdot\cdot\cdot q_{s}.\]

        where \(p_{1}p_{2} \cdot\cdot\cdot p_{r}\) and \(q_{1}q_{2} \cdot\cdot\cdot q_{s}\) are primes with \(p_1 \le p_2 \le \cdot\cdot\cdot p_r\) and \(q_1 \le q_2 \le \cdot\cdot\cdot \le q_s\). Then \(r = s\), and for each \(j\) from 1 to \(r\), \(p_j = q_j\).

    • Theorem 8.16. There are infinitely many prime numbers.

    • Theorem 8.22. Let a, b, and c be integers with \(a \ne 0\) and \(b \ne 0\), and let \(d = \text{gcd}(a, b)\).

      1. If \(d\) does not divide \(c\), then the linear Diophantine equation \(ax + by = c\) has no solution.

      2. If \(d\) divides \(c\), then the linear Diophantine equation \(ax + by = c\) has infinitely many solutions. In addition, if (\(x_0, y_0\)) is a particular solution of this equation, then all the solutions of the equation are given by

      \[x = x_0 + \dfrac{b}{d} k\ \ \ \ \text{and}\ \ \ \ y = y_0 - \dfrac{a}{d} k.\]

      where \(k \in \mathbb{Z}\).

    • Corollary8.23. Let \(a\), \(b\), and \(c\) be integers with \(a \ne 0\) and \(b \ne 0\). If \(a\) and \(b\) are relatively prime, then the linear Diophantine equation \(ax + by = c\) has infinitely many solutions. In addition, if \(x_0\), \(y_0\) is a particular solution of this equation, then all the solutions of the equation are given by

      \[x = x_0 + bk\ \ \ \ \text{and}\ \ \ \ y = y_0 - ak,\]page468image4254810384page468image4254810656page468image4254810928

      where \(k \in \mathbb{Z}\).