Essentials of Number Theory

Chapter 1: What is number theory?

Page 000007

At first glance the term “number theory” seems mysteriously broad. Isn’t all of mathematics about numbers? Is this just another name for mathematics in general? A more cautious reader might note that geometry and logic (for example) aren’t really about numbers, even if numbers are sometimes used. But even leaving out these topics, the “study of numbers” still sounds overly broad. Indeed, the term number theory is traditional, and refers exclusively to the study of whole numbers; that is, the numbers we count with:

1, 2, 3, 4, ...

along with the daring addition of 0, and, when convenient, the negative integers. Excluded from consideration are fractions, real numbers, and complex numbers. Those abstractions, while called numbers in ordinary language, are traditionally studied in courses on Analysis.

While the whole numbers have their origins in counting, number theory is not about counting either. The study of advanced techniques in counting is a field of mathematics all its own, called Combinatorics. Number theory then is the pure study of whole numbers and their relations to one another, especially with regards to addition and multiplication, both of which will always transform whole numbers into whole numbers. For a sense of what this means, consider the following questions about whole numbers:

• Is the sum of two odd numbers even or odd? What about the product?
• If we divide n by 3, we have 2 left over. If we divide the same number n by 17, we have 9 left over. What are the possible values for n?
• Can a power of two ever end in the digits “...324”?
• When can a positive integer n be written as a sum of two integer squares?
• Is the number $1+{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n}}$ ever a whole number if n > 1?
• Does the equation $12x-57y=39$ have integer solutions x and y? What if 39 is replaced with 38?

Number theory, as described so far, may seem a rather abstract topic to spend months (years?) studying. Indeed, because of its ostensible purity and great distance from industrial or scientific applications, number theory was once known as the “Queen of Mathematics.”

Page 000008

This is no longer the case. While still considered an exemplar of abstract mathematical elegance, number theory now provides concrete applications to information theory and computer science, including cryptography, data compression, error-correcting codes, and pseudorandom number generation, to name just a few examples.

All the same, the most compelling reason to study number theory is for its unique combination of simplicity and mystifying complexity, which provides a setting for mathematical beauty, surprise, and the sudden clarity that can be so thrilling to those who enjoy mathematics.

Chapter 2: Integers and arithmetic

Page 000009

Our primary setting is the set Z of integers; that is, whole numbers, positive and negative:

Z = {..., −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, ...}

It is also convenient to denote by N the set of natural numbers; that is, the positive integers:

N = {1, 2, 3, 4, 5, 6, 7, 8, ...}

We will assume familiarity with properties of the integers that the reader should recall from grade school. In particular, the integers have an ordering, and they are closed under addition, subtraction, and multiplication. Moreover, we will also assume that N is closed under addition and multiplication.

The following identities summarize the algebraic properties of the integers.

Theorem 2.1 (Basic properties of integer arithmetic)

Let $a,b,c\in Z$.

• $a+b=b+a$ (Addition is commutative.)
• $a+(b+c)=(a+b)+c$ (Addition is associative.)
• $a+0=a$ (Zero is the additive identity.)
• $a+(-a)=0$ (Every integer has an additive inverse.)
• $ab=ba$ (Multiplication is commutative.)
• $a(bc)=(ab)c$ (Multiplication is associative.)
• $a*1=a$ (One is the multiplicative identity.)
• $a(b+c)=ab+ac$ (Distributive law)
• If $ab=0$ then either a = 0 or b = 0 (or both). (Integral domain)

The last property in the list above implies the following Cancellation Law.

Proposition 2.2 Let $a,b,c\in Z$, and suppose that a ≠ 0. If $ab=ac$ then $b=c$.

Proof. Since $ab=ac$, we have $ab-ac=0$. Since a ≠ 0, the last property in Theorem 2.1 implies that $b-c=0$, so that $b=c$.

Notice what we did not say in the proof above. We did not talk about “dividing both sides by a”. Instead, the proof used properties of addition, subtraction,

Page 000010

and multiplication, without any direct reference to division. The reason for this circumlocution will become evident as the theory unfolds.