Theorems and Corollaries in Elementary Number Theory

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.

45. Lemma Related to $4n + 1$

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

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