$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 8.S: Topics in Number Theory (Summary)

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\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,$   where $$k \in \mathbb{Z}$$.