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.

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\).

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)\).

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.

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\).

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

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

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

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

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

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}\).