Chapter 1. Foundations of Arithmetic

The natural numbers arise from the basic act of counting. When we count objects in a collection, we assign successive numbers:

46 items

Section	Title
1	Chapter 1. Foundations of Arithmetic
2	The Integers
3	Arithmetic Operations
4	Order Relations
5	Absolute Value and Distance
6	Mathematical Induction
7	Strong Induction
8	Recursive Definitions
9	Growth of Integers
10	Historical Development of Number Systems
11	Divisibility Relations
12	Prime Numbers
13	Composite Numbers
14	The Division Algorithm
15	Greatest Common Divisors
16	Least Common Multiples
17	Euclidean Algorithm
18	Extended Euclidean Algorithm
19	Bezout Identities
20	Coprime Integers
21	Unique Prime Factorization
22	Canonical Prime Decomposition
23	Arithmetic Functions from Factorization
24	Infinitude of Primes
25	Euclid's Proof
26	Euler's Proof
27	Distribution Heuristics of Primes
28	Congruence Relations
29	Residue Classes
30	Arithmetic Modulo $n$
31	Linear Congruences
32	Modular Inverses
33	Systems of Congruences
34	Chinese Remainder Theorem
35	Fast Modular Exponentiation
36	Applications to Computation
37	Divisor Functions
38	Möbius Function
39	Euler Totient Function
40	Liouville Function
41	Completely Multiplicative Functions
42	Dirichlet Convolution
43	Möbius Inversion
44	Average Orders of Arithmetic Functions
45	Dirichlet Series
46	Euler Products

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Chapter 1. Foundations of Arithmetic

The natural numbers arise from the basic act of counting. When we count objects in a collection, we assign successive numbers:

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

The Integers

The natural numbers are sufficient for counting and addition, but they are not sufficient for subtraction. For example,

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Arithmetic Operations

An arithmetic operation is a rule that combines numbers to produce another number. The most basic operations on integers are addition, subtraction, multiplication, and division.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Order Relations

The integers are not merely a collection of numbers equipped with arithmetic operations. They also possess an order structure. Given two integers $a$ and $b$, one can...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Absolute Value and Distance

The order relation distinguishes positive and negative integers, but in many situations the sign of a number is less important than its magnitude. For example, the integers

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Mathematical Induction

Many statements in number theory concern all natural numbers. For example, one may wish to prove that

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Strong Induction

Ordinary induction proves a statement $Pn$ by showing that truth passes from one case to the next:

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Recursive Definitions

Many mathematical objects are defined recursively. A recursive definition specifies:

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Growth of Integers

The integers extend infinitely in both directions:

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Historical Development of Number Systems

The idea of number arose long before formal mathematics. Early civilizations used numbers for counting objects, measuring land, recording trade, and tracking time.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Divisibility Relations

Division of integers does not always produce an integer. For example,

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Prime Numbers

Prime numbers are the fundamental building blocks of arithmetic.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Composite Numbers

A positive integer $n>1$ is called composite if it is not prime.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

The Division Algorithm

The division algorithm is one of the basic structural facts about the integers. It says that any integer can be divided by a positive integer with a unique quotient and remainder.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Greatest Common Divisors

Let $a$ and $b$ be integers, not both zero. An integer $d$ is called a common divisor of $a$ and $b$ if

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Least Common Multiples

Let $a$ and $b$ be nonzero integers. An integer $m$ is called a common multiple of $a$ and $b$ if

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Euclidean Algorithm

The greatest common divisor of two integers can be found by listing divisors, but this method becomes inefficient for large numbers. For example, finding

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Extended Euclidean Algorithm

The Euclidean algorithm computes the greatest common divisor of two integers. The extended Euclidean algorithm does more. It also expresses the gcd as an integer linear...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Bezout Identities

Let $a$ and $b$ be integers. An integer of the form

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Coprime Integers

Two integers $a$ and $b$, not both zero, are called coprime if their greatest common divisor is $1$:

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Unique Prime Factorization

The fundamental theorem of arithmetic states that every integer $n>1$ can be written as a product of prime numbers, and that this product is unique up to the order of the factors.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Canonical Prime Decomposition

Unique prime factorization says that every integer $n>1$ can be written as a product of primes. The canonical prime decomposition is the ordered and exponentiated version of...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Arithmetic Functions from Factorization

An arithmetic function is a function whose domain is the positive integers. It assigns a value to each integer

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Infinitude of Primes

Prime numbers are the building blocks of the positive integers. Once unique prime factorization is known, a natural question arises: are there only finitely many primes, or do...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Euclid's Proof

Euclid's proof of the infinitude of primes is one of the earliest examples of a general argument in number theory. It does not depend on computation, experimentation, or...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Euler's Proof

Euclid proved that there are infinitely many primes by contradiction. Euler discovered a very different proof based on infinite series and products.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Distribution Heuristics of Primes

The infinitude of primes guarantees that primes continue indefinitely, but it says nothing about how frequently primes occur.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Congruence Relations

Ordinary equality compares integers exactly. In many arithmetic problems, however, only the remainder after division matters.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Residue Classes

Congruence modulo $n$ groups integers according to their remainders after division by $n$. If two integers have the same remainder, they are congruent modulo $n$.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Arithmetic Modulo $n$

Arithmetic modulo $n$ is arithmetic performed on residue classes modulo $n$. Instead of distinguishing all integers separately, we identify integers that have the same...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Linear Congruences

A linear congruence is a congruence of the form

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Modular Inverses

In ordinary arithmetic, division by a nonzero number means multiplication by its reciprocal. Modular arithmetic is more delicate. A residue class may or may not have a...

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Systems of Congruences

A system of congruences asks for an integer satisfying several congruence conditions simultaneously.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Chinese Remainder Theorem

The Chinese remainder theorem describes when several congruence conditions can be combined into one congruence. Its cleanest form occurs when the moduli are pairwise coprime.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Fast Modular Exponentiation

Modular arithmetic often requires computing powers such as

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Applications to Computation

Modular arithmetic is not only a theoretical language for divisibility. It is also one of the main tools of computation with integers.

Writes › Book › Modern Number Theory › Chapter 1. Foundations of Arithmetic ›

Divisor Functions

Divisor functions measure the positive divisors of an integer. They are among the first examples of arithmetic functions, because their values depend directly on the prime...