# Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)

All theorems and corollaries mentioned in David M. Burton's Elementary Number Theory are listed by following the book's order. (7th Edition) (Currently Ch 1 - 3)

This article will list all theorems and corollaries mentioned in David M. Burton's Elementary Number Theory.

I have been learning number theory by using this book. The theorems and corollaries listed here will follow the book's order. I think this will be helpful for people who are also learning through this book because you can use this list as a reference when trying to solve each chapter's problems.

If you are interested in buying this book for learning number theory, you can check it out at the link below (Amazon/Book Depository).

I think it is a pretty good number theory book for beginners.

## Chapter 1 Preliminaries

### Section 1.1 Mathematical Induction

#### 1. Well-Ordering Principle

Every nonempty set $$S$$ of nonnegative integers contains a least element; that is, there is some integer $$a$$ in $$S$$ such that $$a \le b$$ for all $$b$$'s belonging to $$S$$.

#### 2. Theorem 1.1 Archimedean property

If $$a$$ and $$b$$ are any positive integers, then there exists a positive integer $$n$$ such that $$na \leq b$$

#### 3. Theorem 1.2 First Principle of Finite Induction

Let $$S$$ be a set of positive integers with the following properties:

(a) The integer 1 belongs to $$S$$

(b) Whenever the integer $$k$$ is in $$S$$, the next integer $$k + 1$$ must also be in $$S$$.

Then $$S$$ is the set of all positive integers.

#### 4. Variant of Theorem 1.2 Second Principle of Finite Induction

(a) The integer 1 belongs to $$S$$.

(b) If $$k$$ is a positive integer such that 1, 2, ... , $$k$$ belong to $$S$$, then $$k + 1$$ must also be in $$S$$.

Then $$S$$ is the set of all positive integers.

### Section 1.2 The Binomial Theorem

#### 5. Pascal's rule (Chapter 1.2)

${n \choose k} + {n \choose k - 1} = {n + 1 \choose k}$

#### 6. Binomial Theorem

$(a+b)^{n} = \sum_{k=0}^n {n \choose k} a^{n-k}b^{k}$

## Chapter 2 Divisibility Theory in the Integers

### Section 2.2 The Division Algorithm

#### 7. Theorem 2.1 Division Algorithm

Given integers $$a$$ and $$b$$, with $$b \gt 0$$, there exist unique integers $$q$$ and $$r$$ satisfying
$a = qb + r \quad 0 \le r \lt b$

#### 8. Corollary of Theorem 2.1

If $$a$$ and $$b$$ are integers, with $$b \neq 0$$, then there exist unique integers $$q$$ and $$r$$ such that
$a = qb + r \quad 0 \le r \lt \lvert b\rvert$

### Section 2.3 The Greatest Common Divisor

#### 9. Definition of Divisibility (Definition 2.1)

An integer $$b$$ is said to be divisible by an integer $$a \neq 0$$, in symbols $$a \mid b$$, if there exists some integer $$c$$ such that $$b = ac$$. We write $$a \nmid b$$ to indicate that $$b$$ is not divisible by $$a$$.

#### 10. Theorem 2.2

For integers $$a$$, $$b$$, $$c$$, the following hold:

(a) $$a \mid 0,\ 1 \mid a,\ a \mid a.$$
(b) $$a \mid 1$$ if and only if $$a = \pm 1$$.
(c) If $$a \mid b$$ and $$c \mid d$$, then $$ac \mid bd$$.
(d) If $$a \mid b$$ and $$b \mid c$$, then $$a \mid c$$.
(e) $$a \mid b$$ and $$b \mid a$$ if and only if $$a = \pm b$$.
(f) If $$a \mid b$$ and $$b \neq 0$$, then $$\lvert a \rvert \le \lvert b \vert$$.
(g) If $$a \mid b$$ and $$a \mid c$$, then $$a \mid (bx + cy)$$ for arbitrary integers $$x$$ and $$y$$.

#### 11. Definition of GCD (Definition 2.2)

Let $$a$$ and $$b$$ be given integers, with at least one of them different from zero. The greatest common divisor of $$a$$ and $$b$$, denoted by $$gcd(a, b)$$, is the positive integer $$d$$ satisfying the following:

(a) $$d \mid a$$ and $$d \mid b$$.

(b) If $$c \mid a$$ and $$c \mid b$$, then $$c \le d$$.

#### 12. Theorem 2.3

Given integers $$a$$ and $$b$$, not both of which are zero, there exist integers $$x$$ and $$y$$ such that
$gcd(a, b) = ax + by$

#### 13. Corollary of Theorem 2.3

If $$a$$ and $$b$$ are given integers, not both zero, then the set
$T = \{ax + by \ \vert \ x,y\ are\ integers\}$
is precisely the set of all multiples of $$d = gcd(a, b)$$.

#### 14. Definition of Relatively Prime

Two integers $$a$$ and $$b$$, not both of which are zero, are said to be relatively prime whenever $$gcd(a, b) = 1$$.

#### 15. Theorem 2.4

Let $$a$$ and $$b$$ be integers, not both zero. Then $$a$$ and $$b$$ are relatively prime if and only if there exist integers $$x$$ and $$y$$ such that $$1 = ax + by$$.

#### 16. Corollary 1 of Theorem 2.4

If $$gcd(a, b) = d$$, then $$gcd(a/d, b/d) = 1$$.

#### 17. Corollary 2 of Theorem 2.4

If $$a \mid c$$ and $$b \mid c$$, with $$gcd(a, b) = 1$$, then $$ab \mid c$$.

#### 18. Theorem 2.5 Euclid's lemma.

If $$a \mid bc$$, with $$gcd(a, b) = 1$$, then $$a \mid c$$.

#### 19. Theorem 2.6 (Another Definition of GCD without Order Relation)

Let $$a$$, $$b$$ be integers, not both zero. For a positive integer $$d$$, $$d = gcd(a, b)$$ if and only if

(a) $$d \mid a$$ and $$d \mid b$$.

(b) Whenever $$c \mid a$$ and $$c \mid b$$, then $$c \mid d$$.

### Section 2.4 The Euclidean Algorithm

#### 20. Euclidean Algorithm's Lemma

If $$a = qb + r$$, then $$gcd(a, b) = gcd(b, r)$$.

#### 21. Theorem 2.7

If $$k \gt 0$$, then $$gcd(ka,kb) = k \ gcd(a,b)$$.

#### 22. Corollary of Theorem 2.7

For any integer $$k \neq 0$$, $$gcd(ka, kb) = \lvert k\rvert\ gcd(a, b)$$.

#### 23. Definition 2.4 (Definition of LCM)

The least common multiple of two nonzero integers $$a$$ and $$b$$, denoted by $$lcm(a,b)$$, is the positive integer $$m$$ satisfying the following:

(a) $$a \mid m$$ and $$b \mid m$$.

(b) If $$a \mid c$$ and $$b \mid c$$, with $$c \gt 0$$, then $$m \leq c$$.

#### 24. Theorem 2.8

For positive integers $$a$$ and $$b$$
$gcd(a, b)\ lcm(a, b) = ab$

#### 25. Corollary of Theorem 2.8

For any choice of positive integers $$a$$ and $$b$$, $$lcm(a, b) = ab$$ if and only if $$gcd(a, b) = 1$$.

### Section 2.5 The Diophantine Equation ax + by = c

#### 26. Theorem 2.9

The linear Diophantine equation $$ax + by = c$$ has a solution if and only if $$d \mid c$$, where $$d = gcd(a, b)$$. If $$x_0$$, $$y_0$$ is any particular solution of this equation, then all other solutions are given by
$x = x_0 + (\frac{b}{d})t \qquad y = y_0 - (\frac{a}{d})t$
where $$t$$ is an arbitrary integer.

#### 27. Corollary of Theorem 2.9

If $$gcd(a, b) = 1$$ and if $$x_0$$, $$y_0$$ is a particular solution of the linear Diophantine equation $$ax + by = c$$, then all solutions are given by
$x = x_0 + bt \qquad y = y_0 - at$
for integral values of $$t$$.

## Chapter 3 Primes and Their Distribution

### Section 3.1 The Fundamental Theorem of Arithmetic

#### 28. Definition 3.1

An integer $$p \gt 1$$ is called a prime number, or simply a prime, if its only positive divisors are $1$ and $$p$$. An integer greater than 1 that is not a prime is termed composite.

#### 29. Theorem 3.1

If $$p$$ is a prime and $$p \mid ab$$, then $$p \mid a$$ or $$p \mid b$$.

#### 30. Corollary 1 of Theorem 3.1

If $$p$$ is a prime and $$p \mid a_{1}a_{2} \cdots a_{n}$$, then $$p \mid a_{k}$$ for some $$k$$, where $$1 \leq k \leq n$$.

#### 31. Corollary 2 of Theorem 3.1

If $$p, q_{i}, q_{2}, \cdots , q_{n}$$ are all primes and $$p \mid q_{1}q_{2} · · · q_{n}$$, then $$p = q_{k}$$ for some $$k$$, where $$1 \leq k \leq n$$.

#### 32. Theorem 3.2 Fundamental Theorem of Arithmetic

Every positive integer $$n \gt 1$$ is either a prime or a product of primes; this representation is unique, apart from the order in which the factors occur.

#### 33. Corollary of Theorem 3.2

Any positive integer $$n > 1$$ can be written uniquely in a canonical form
$n = p_{1}^{k_1}p_{2}^{k_2} \cdots p_{r}^{k_r}$
where, for $$i = 1, 2, ... , r,$$ each $$k_{i}$$ is a positive integer and each $$p_{i}$$ is a prime, with $$p_1 \lt p_2 \lt \cdots \lt p_r .$$

#### 34. Theorem 3.3 Pythagoras

The number $\sqrt{2}$ is irrational.

### Section 3.2 The Sieve Of Eratosthenes

#### 35. Property of Composite Numbers

(This is mentioned in a paragraph of the section on page 44, but it is very important.)

A composite number $a$ will always possess a prime divisor $p$ satisfying $p \leq \sqrt{a}$.

#### 36. Definition of the Sieve of Eratosthenes

(This is mentioned in the second paragraph of the section on Page 45.)

The scheme calls for writing down the integers from $2$ to $n$ in their natural order and then systematically eliminating all the composite numbers by striking out all multiples $2p$, $3p$, $4p$, $5p$, ... of the primes $p \leq n$. The integers that are left on the list—those that do not fall through the "sieve"-are primes.

#### 37. Theorem 3.4 Euclid

There is an infinite number of primes.

#### 38. Theorem 3.5

If $p_{n}$ is the $n$th prime number, then $p_{n} \leq 2^{2^{n} - 1}$.

#### 39. Corollary of Theorem 3.5

For $n \geq 1$, there are at least $n + 1$ primes less than $2^{2^{n}}$.

#### 40. Joseph Bertrand's Postulate

There exists at least one prime number between $n \geq 2$ and $2n$.

#### 41. Direct Consequence From Bertrand's Postulate

$$p_{n} < 2^n \quad n \geq 2$$Also, this implies that $p_{n+1} < 2p_{n}$.

#### 42. Definition of Repunit Number

A $\textit{repunit}$ is an integer written (in decimal notation) as a string of $1$'s, such as $11$, $111$, or $1111$. Each such integer must have the form $\frac{(10^n - 1)}{9}$. We use the symbol $R_{n}$ to denote the repunit consisting of $n$ consecutive $1$'s.

### Section 3.3 The Goldbach Conjecture

#### 43. Definition of Twin Prime

(This is mentioned in the second paragraph of the section on Page 50.)

Twin primes are pairs of successive odd integers $p$ and $p + 2$ that are both primes.

#### 44. Definition of Goldbach Conjecture

(This is mentioned in the last paragraph of the section on Page 51.)

Every even integer greater than $4$ can be written as a sum of two odd prime numbers.

The product of two or more integers of the form $4n + 1$ is of the same form.

#### 46. Theorem 3.6

There are an infinite number of primes of the form $4n + 3$.

#### 47. Theorem 3.7 Dirichlet.

If $a$ and $b$ are relatively prime positive integers, then the arithmetic progression $$a, a + b, a+ 2b, a+ 3b, ...$$ contains infinitely many primes.

#### 48. Theorem 3.8

If all the $n \gt 2$ terms of the arithmetic progression $$p, p + d, p + 2d, ... , p + (n - 1)d$$ are prime numbers, then the common difference $d$ is divisible by every prime $q < n$.

## Chapter 4 The Theory of Congruences

### Section 4.2 Basic Properties of Congruence

#### 49. Definition 4.1 Definition of Congruence

Let $n$ be a fixed positive integer. Two integers $a$ and $b$ are said to be \textit{congruence modulo} $n$, symbolized by $$a \equiv b \pmod n$$ if $n$ divides the difference $a - b$; that is, provided that $a - b = kn$ for some integer $k$.

Number TheoryMath