# 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: $$ \mathbb{N}=\{1,2,3,\ldots\} $$ $$ \mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\} $$ $$ \mathbb{Q}=\left\{\frac{a}{b}:a,b\in\mathbb{Z}, b\ne 0\right\} $$ 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 $$ A \subseteq B $$ means $$ x \in A \implies x \in B. $$ For example, $$ \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}. $$ Two sets are equal when each is contained in the other: $$ A=B \quad \Longleftrightarrow \quad A\subseteq B \text{ and } B\subseteq A. $$ 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 $$ A\cup B=\{x:x\in A \text{ or } x\in B\}. $$ Their intersection is $$ A\cap B=\{x:x\in A \text{ and } x\in B\}. $$ Their difference is $$ A\setminus B=\{x:x\in A \text{ and } x\notin B\}. $$ If the ambient set is fixed, the complement of $A$ is $$ A^c=\{x:x\notin A\}. $$ 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. $$ \varnothing \subseteq A $$ 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 $$ A\times B=\{(a,b):a\in A,\ b\in B\}. $$ Elements of $A\times B$ are ordered pairs. Order matters: $$ (a,b)=(c,d) $$ if and only if $$ a=c \quad \text{and} \quad b=d. $$ 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 $$ x^2+y^2=z^2 $$ 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 $$ aRb. $$ Important examples include equality, order, divisibility, and congruence. Divisibility is a relation on $\mathbb{Z}$. We write $$ a\mid b $$ if there exists an integer $k$ such that $$ b=ak. $$ Congruence modulo $n$ is also a relation on $\mathbb{Z}$. We write $$ a\equiv b \pmod n $$ if $$ n\mid(a-b). $$ ## A.7 Equivalence Relations An equivalence relation on a set $A$ is a relation $\sim$ satisfying three properties. Reflexivity: $$ a\sim a. $$ Symmetry: $$ a\sim b \implies b\sim a. $$ Transitivity: $$ a\sim b,\ b\sim c \implies a\sim c. $$ Congruence modulo $n$ is the central example: $$ a\equiv b \pmod n. $$ 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 $$ [a]=\{x\in A:x\sim a\}. $$ For congruence modulo $n$, $$ [a]=\{x\in\mathbb{Z}:x\equiv a\pmod n\}. $$ The set of all residue classes modulo $n$ is written $$ \mathbb{Z}/n\mathbb{Z}. $$ 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 $$ f(A)=\{f(a):a\in A\}. $$ A function is injective if $$ f(a)=f(a') \implies a=a'. $$ 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 $$ P\implies Q $$ means that whenever $P$ is true, $Q$ is true. The statement $$ P\Longleftrightarrow Q $$ means that $P$ and $Q$ are equivalent. The universal quantifier $\forall$ means “for all.” The existential quantifier $\exists$ means “there exists.” For example, $$ \forall n\in\mathbb{Z},\quad n^2\ge 0 $$ says that every integer has a nonnegative square. The statement $$ \exists p\in\mathbb{N}\quad \text{such that } p \text{ is prime} $$ 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 $$ \forall x\in A,\ P(x) $$ is $$ \exists x\in A \text{ such that } \neg P(x). $$ The negation of $$ \exists x\in A \text{ such that } P(x) $$ is $$ \forall x\in A,\ \neg P(x). $$ 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 $$ p_1,p_2,\ldots,p_k. $$ Consider $$ N=p_1p_2\cdots p_k+1. $$ 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 $$ P\implies Q $$ is $$ \neg Q\implies \neg P. $$ These two statements are logically equivalent. For example, to prove $$ n^2 \text{ even } \implies n \text{ even}, $$ one may prove the contrapositive: $$ n \text{ odd } \implies n^2 \text{ odd}. $$ If $n=2k+1$, then $$ n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1, $$ 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 $1N \text{ such that } p \text{ is prime}. $$ The statement “every nonzero integer has only finitely many divisors” means: $$ \forall n\in\mathbb{Z},\ n\ne 0 \implies \{d\in\mathbb{Z}:d\mid n\} \text{ is finite}. $$ Writing statements in quantified form removes ambiguity. It also clarifies what must be proved and what may be assumed. ## A.17 Common Notation | Symbol | Meaning | |---|---| | $x\in A$ | $x$ is an element of $A$ | | $x\notin A$ | $x$ is not an element of $A$ | | $A\subseteq B$ | $A$ is a subset of $B$ | | $A\cup B$ | union | | $A\cap B$ | intersection | | $A\setminus B$ | difference | | $\varnothing$ | empty set | | $A\times B$ | Cartesian product | | $\forall$ | for all | | $\exists$ | there exists | | $\implies$ | implies | | $\Longleftrightarrow$ | if and only if | | $\neg P$ | not $P$ | | $\mathbb{N}$ | natural numbers | | $\mathbb{Z}$ | integers | | $\mathbb{Q}$ | rational numbers | | $\mathbb{R}$ | real numbers | | $\mathbb{C}$ | complex numbers |