# Theorems and Corollaries in Elementary Number Theory

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 - 4)

This article will list all theorems and corollaries mentioned in David M. Burton's Elementary Number Theory. (Currently contains Chapter 1 - 4)

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$.

#### 50. A Complete Set of Residues

A collection of $n$ integers $a_{1}, a_{2}, ... , a_{n}$ is said to form a complete set of residues (or a complete system of residues) modulo $n$ if every integer is congruent modulo $n$ to one and only one of the $a_{k}$.

(Note and Example:
To put it another way, $a_{1}, a_{2}, ... , a_{n}$ are congruent modulo $n$ to $0, 1, 2, ... , n - 1,$ taken in some order. For instance, $$-12, -4, 11, 13, 22, 82, 91$$ constitute a complete set of residues modulo $7$; here, we have $$-12 \equiv 2 \quad -4 \equiv 3 \quad 11 \equiv 4 \quad 13 \equiv 6 \quad 22 \equiv 1 \quad 82 \equiv 5 \quad 91 \equiv 0$$)

#### 51. Observation From A Complete Set of Residues

A complete set of residues modulo $n$ if and only if no two of the integers are congruent modulo $n$.

#### 52. Theorem 4.1

For arbitrary integers $a$ and $b$, $a \equiv b \pmod n$ if and only if $a$ and $b$ leave the same nonnegative remainder when divided by $n$.

#### 53. Theorem 4.2

Let $n > 1$ be fixed and $a, b, c, d$ be arbitrary integers. Then the following properties hold:
(a) $a \equiv a \pmod n$.
(b) If $a \equiv b \pmod n$, then $b \equiv a \pmod n$.
(c) If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a \equiv c \pmod n$.
(d) If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $a + c \equiv b + d \pmod n$ and $ac \equiv bd \pmod n$.
(e) If $a \equiv b \pmod n$, then $a+ c \equiv b + c \pmod n$ and $ac \equiv bc \pmod n$.
(f) If $a \equiv b \pmod n$, then $a^{k} \equiv b^{k} \pmod n$ for any positive integer $k$.

#### 54. Theorem 4.3

If $ca \equiv cb \pmod n$, then $a \equiv b \pmod {n/d}$, where $d = gcd(c, n)$.

#### 55. Corollary 1 of Theorem 4.3

If $ca \equiv cb \pmod n$ and $gcd(c, n) = 1$, then $a \equiv b \pmod n$.

#### 56. Corollary 2 of Theorem 4.3

If $ca \equiv cb \pmod p$ and $p \not \mid c$, where $p$ is a prime number, then $a \equiv b \pmod p$.

### Section 4.3 Binary and Decimal Representations of Integers

#### 57. Representation of Integers

Given an integer $b > 1$, any positive integer $N$ can be written uniquely in terms of powers of $b$ as $$N = a_{m}b^{m} + a_{m - 1}b^{m - 1} + \cdots + a_{2}b^{2} + a_{1}b + a_{0}$$

where the coefficients $a_{k}$ can take on the $b$ different values $0, 1, 2, ... , b - 1$.

#### 58. Simpler Symbol

$$N = (a_{m}a_{m-1} \cdots a_{2}a_{1}a_{0})_{b}$$

#### 59. Binary Exponential Algorithm

In order to calculate the value of $a^{k} \pmod {n}$ when $k$ is large, we can use binary exponential algorithm. The exponent $k$ is written in binary form, as $k = (a^{m}a^{m-1} ... a^{2}a^{1}a^{0})_{2}$, and the values $a^{2^{j}} \pmod {n}$ are calculated for the powers of $2$, which correspond to the $1$'s in the binary representation. These partial results are then multiplied together to give the final answer.

Example:

To calculate $5^{110} \pmod {131}$, we note that $110 = 64 + 32 + 8 + 4 + 2 = (1101110)_{2}$.

Thus

$$$$\begin{split} 5^{110} & = 5^{64 + 32 + 8 + 4 + 2} \\ & \equiv 5^{64} \cdot 5^{32} \cdot 5^{8} \cdot 5^{4} \cdot 5^{2} \\ & \equiv 105 \cdot 74 \cdot 114 \cdot 101 \cdot 25 \\ & \equiv 60 \pmod {131} \end{split} \nonumber$$$$

#### 60. Theorem 4.4

Let $P(x) = \sum_{k=0}^{m} c_{k}x^{k}$ be a polynomial function of $x$ with integral coefficients $c_{k}$. If $a \equiv b \pmod {n}$, then $P(a) \equiv P(b) \pmod {n}$.

#### 61. Corollary of Theorem 4.4

If $a$ is a solution of $P(x) \equiv 0 \pmod {n}$ and $a \equiv b \pmod {n}$, then $b$ also is a solution.

#### 62. Theorem 4.5

Let $N = a_{m}10^{m} + a_{m - 1}10^{m - 1} + \cdots + a_{1}10 + a_{0}$ be the decimal expansion of the positive integer $N$, $0 \leq a_{k} < 10$, and let $S = a_{0} + a_{1} + \cdots + a_{m}$. Then $9 \mid N$ if and only if $9 \mid S$.

#### 63. Theorem 4.6

Let $N = a_{m}10^{m} + a_{m - 1}10^{m - 1} + \cdots + a_{1}10 + a_{0}$ be the decimal expansion of the positive integer $N$, $0 \leq a_{k} < 10$, and let $T = a_{0} - a_{1} + a_{2} - \cdots + (-1)^{m}a_{m}$. Then $11 \mid N$ if and only if $11 \mid T$.

Number TheoryMath