Appendix

A.1 Sets

A set is a collection of objects, called its elements. If $x$ is an element of a set $A$, we write $x \in A$. If $x$ is not an element of $A$, we write $x \notin A$.

Examples:

In number theory, sets usually describe domains of arithmetic objects: integers, primes, residue classes, ideals, rational points, or solutions to equations.

A.2 Subsets

A set $A$ is a subset of a set $B$, written $A \subseteq B$, if every element of $A$ also belongs to $B$. Thus

means

For example,

Two sets are equal when each is contained in the other:

This criterion is often the cleanest way to prove equality of sets.

A.3 Basic Set Operations

Given two sets $A$ and $B$, their union is

Their intersection is

Their difference is

If the ambient set is fixed, the complement of $A$ is

For example, if the ambient set is $\mathbb{Z}$, then the complement of the even integers is the set of odd integers.

A.4 Empty Set and Universal Set

The empty set, written $\varnothing$, contains no elements. It is a subset of every set.

for every set $A$.

A universal set is the ambient set under discussion. In elementary number theory, the universal set is often $\mathbb{Z}$, $\mathbb{N}$, or $\mathbb{Z}/n\mathbb{Z}$. The choice matters. For example, the complement of the primes differs depending on whether the ambient set is $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{R}$.

A.5 Cartesian Products

The Cartesian product of $A$ and $B$ is

Elements of $A\times B$ are ordered pairs. Order matters:

if and only if

Cartesian products appear naturally in number theory when studying pairs of integers, lattice points, congruence systems, and rational points on curves.

For example, solutions to

may be studied as triples $(x,y,z)\in\mathbb{Z}^3$.

A.6 Relations

A relation on a set $A$ is a subset of $A\times A$. If $R$ is a relation and $(a,b)\in R$, we often write

Important examples include equality, order, divisibility, and congruence.

Divisibility is a relation on $\mathbb{Z}$. We write

if there exists an integer $k$ such that

Congruence modulo $n$ is also a relation on $\mathbb{Z}$. We write

if

A.7 Equivalence Relations

An equivalence relation on a set $A$ is a relation $\sim$ satisfying three properties.

Reflexivity:

Symmetry:

Transitivity:

Congruence modulo $n$ is the central example:

It is reflexive, symmetric, and transitive. Therefore it partitions $\mathbb{Z}$ into equivalence classes, called residue classes modulo $n$.

A.8 Equivalence Classes

If $\sim$ is an equivalence relation on $A$, the equivalence class of $a\in A$ is

For congruence modulo $n$,

The set of all residue classes modulo $n$ is written

This notation is fundamental in modern number theory. It replaces individual integers by their arithmetic behavior modulo $n$.

A.9 Functions

A function $f:A\to B$ assigns to each element $a\in A$ exactly one element $f(a)\in B$.

The set $A$ is the domain. The set $B$ is the codomain. The image of $f$ is

A function is injective if

It is surjective if every element of $B$ occurs as $f(a)$ for some $a\in A$.

It is bijective if it is both injective and surjective.

Bijective functions identify two sets as having the same size or structure.

A.10 Logic and Quantifiers

Mathematical statements are built from propositions using logical connectives.

The statement

means that whenever $P$ is true, $Q$ is true.

The statement

means that $P$ and $Q$ are equivalent.

The universal quantifier $\forall$ means “for all.” The existential quantifier $\exists$ means “there exists.”

For example,

says that every integer has a nonnegative square.

The statement

says that at least one prime number exists.

A.11 Negation of Quantified Statements

Negating quantified statements is a common source of errors.

The negation of

is

The negation of

is

For example, the negation of “every integer is even” is “there exists an integer that is not even.”

It is not “every integer is odd.”

A.12 Proof by Contradiction

To prove a statement $P$ by contradiction, assume that $P$ is false and derive an impossibility.

A classical example is Euclid’s proof that there are infinitely many primes. Suppose there are only finitely many primes

Consider

No $p_i$ divides $N$, since division by $p_i$ leaves remainder $1$. Hence $N$ has a prime divisor not among the listed primes. This contradicts the assumption that the list contained all primes.

Therefore there are infinitely many primes.

A.13 Proof by Contrapositive

The contrapositive of

is

These two statements are logically equivalent.

For example, to prove

one may prove the contrapositive:

If $n=2k+1$, then

so $n^2$ is odd.

A.14 Mathematical Induction

Mathematical induction proves statements indexed by natural numbers.

To prove $P(n)$ for all $n\ge n_0$, prove:

1. Base case: $P(n_0)$ is true.
2. Inductive step: for every $n\ge n_0$, $P(n)\implies P(n+1)$.

Then $P(n)$ holds for all $n\ge n_0$.

Induction is used throughout number theory: divisibility arguments, recursive sequences, Euclidean algorithm termination, and formulas involving sums or products.

A.15 Strong Induction

Strong induction allows the inductive step to use all earlier cases.

To prove $P(n)$ for all $n\ge n_0$, prove:

1. Base case: $P(n_0)$ is true.
2. Strong inductive step: if $P(n_0),P(n_0+1),\ldots,P(n)$ are true, then $P(n+1)$ is true.

Strong induction is especially useful for factorization. To prove that every integer $n\ge 2$ factors into primes, assume all integers from $2$ up to $n-1$ factor into primes. If $n$ is prime, there is nothing to prove. If $n=ab$ with $1<a,b<n$, then both $a$ and $b$ factor into primes, so $n$ does too.

A.16 Logical Precision in Number Theory

Number theory often turns simple-looking statements into precise logical claims.

For example, the statement “there are infinitely many primes” means:

The statement “every nonzero integer has only finitely many divisors” means:

Writing statements in quantified form removes ambiguity. It also clarifies what must be proved and what may be assumed.

A.17 Common Notation