8.S: Topics in Number Theory (Summary)

Last updated
Save as PDF

Page ID: 7084

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\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}}$ $\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}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

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,\] $page468image4254810384$ $page468image4254810656$ $page468image4254810928$

where $k \in \mathbb{Z}$.