Chapter 1. Foundations of Arithmetic – brain

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

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

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

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

Order RelationsThe 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...

Absolute Value and DistanceThe 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

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

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

Recursive DefinitionsMany mathematical objects are defined recursively. A recursive definition specifies:

Growth of IntegersThe integers extend infinitely in both directions:

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

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

Prime NumbersPrime numbers are the fundamental building blocks of arithmetic.

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

The Division AlgorithmThe 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.

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

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

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

Extended Euclidean AlgorithmThe 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...

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

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

Unique Prime FactorizationThe 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.

Canonical Prime DecompositionUnique 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...

Arithmetic Functions from FactorizationAn arithmetic function is a function whose domain is the positive integers. It assigns a value to each integer

Infinitude of PrimesPrime 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...

Euclid's ProofEuclid'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...

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

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

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

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

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

Linear CongruencesA linear congruence is a congruence of the form

Modular InversesIn 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...

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

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

Fast Modular ExponentiationModular arithmetic often requires computing powers such as

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

Divisor FunctionsDivisor 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...

Möbius FunctionThe Möbius function is an arithmetic function denoted by

Euler Totient FunctionEuler's totient function is an arithmetic function denoted by

Liouville FunctionThe Liouville function is an arithmetic function denoted by

Completely Multiplicative FunctionsAn arithmetic function is a function defined on the positive integers. Such a function

Dirichlet ConvolutionArithmetic functions can be added and multiplied pointwise, but number theory has another product that is better adapted to divisibility.

Möbius InversionMany arithmetic functions are defined through sums over divisors. For example,

Average Orders of Arithmetic FunctionsArithmetic functions often fluctuate strongly from one integer to the next.

Dirichlet SeriesAn arithmetic function $fn$ can be encoded into an infinite series of the form

Euler ProductsEuler products are one of the central ideas of analytic number theory. They express infinite sums over integers as infinite products over primes.