## TJ-AATA 2.1 数学归纳法

**Principle 2.1 First Principle of Mathematical Induction.** Let $S(n)$ be a statement
about integers for $n \in \mathbb{N}$ and suppose $S(n_0)$ is true for some integer $n_0$. If for all integers $k$ with $k \geqslant n_0$, $S(k)$ implies that $S(k + 1)$ is true, then $S(n)$ is true for all integers $n$ greater than or equal to $n_0$.

**Principle 2.5 Second Principle of Mathematical Induction.** Let $S(n)$ be a statement
about integers for $n \in \mathbb{N}$ and suppose $S(n_0)$ is true for some integer $n_0$. If $S(n_0)$, $S(n_0 + 1)$, $\dots$, $S(k)$ imply that $S(k +1)$ for $k \geqslant n_0$, then the statement $S(n)$ is true for all integers $n \geqslant n_0$.

A nonempty subset $S$ of $\mathbb{Z}$ is *well-ordered* if $S$ contains a least element.

**Principle 2.6 Principle of Well-Ordering.** Every nonempty subset of the natural numbers is well-ordered.

**Lemma 2.7.** The Principle of Mathematical Induction implies that 1 is the least positive natural number.

**Theorem 2.8.** The Principle of Mathematical Induction implies the Principle of Well- Ordering. That is, every nonempty subset of $\mathbb{N}$ contains a least element.

## TJ-AATA 2.2 除法算法

**Theorem 2.9 Division Algorithm.** Let $a$ and $b$ be integers, with $b > 0$. Then there exist
unique integers $q$ and $r$ such that
$$a = bq + r$$
where $0 \leqslant r < b$.

Let $a$ and $b$ be integers. If $b = ak$ for some integer $k$, we write $a \mid b$. An integer $d$ is called a *common divisor* of $a$ and $b$ if $d \mid a$ and $d \mid b$.

The *greatest common divisor* of integers $a$ and $b$ is a positive integer $d$ such that $d$ is a common divisor of $a$ and $b$ and if $d′$ is any other common divisor of $a$ and $b$, then $d′ \mid d$. We write $d = \gcd(a, b)$.

We say that two integers $a$ and $b$ are **relatively prime** if $\gcd(a, b) = 1$.

**Theorem 2.10.** Let $a$ and $b$ be nonzero integers. Then there exist integers $r$ and $s$ such
that
$$\gcd(a, b) = ar + bs.$$
Furthermore, the greatest common divisor of $a$ and $b$ is unique.

### 辗转相除法（略）

### 质数

Let $p$ be an integer such that $p > 1$. We say that $p$ is a *prime number*, or simply $p$ is
*prime*, if the only positive numbers that divide $p$ are 1 and $p$ itself. An integer $n > 1$ that is not prime is said to be **composite**.

**Lemma 2.13 Euclid.** Let $a$ and $b$ be integers and $p$ be a prime number. If $p \mid ab$, then
either $p \mid a$ or $p \mid b$.

**Theorem 2.14 Euclid.** There exist an infinite number of primes.

**Theorem 2.15 Fundamental Theorem of Arithmetic.** Let $n$ be an integer such that $n > 1$. Then
$$n = p_1p_2 \dots p_k,$$
where $p_1, \dots, p_k$ are primes (not necessarily distinct). Furthermore, this factorization is
unique; that is, if
$$n = q_1q_2 \dots q_l,$$
then $k = l$ and the $q_i'$s are just the $p_i’$s rearranged.

## CS2.2 逆元与最大公因数

If $a' \dot a \equiv 1 \mod n$, we call $a$ has a **multiplicative inverse** $a'$ in $\mathbb{Z}_n$.

**Lemma 2.5** Suppose $a$ has a multiplicative inverse $a'$ in $\mathbb{Z}_n$. Then for any $b \in \mathbb{Z}_n$, the equation
$$a \cdot_n x = b$$
has the unique solution
$$x = a' \cdot_n b.$$

**Corollary 2.6** Suppose there is a $b$ in $\mathbb{Z}_n$ such that the equation
$$a \cdot_n x = b$$
does not have a solution. Then $a$ does not have a multiplicative inverse in $\mathbb{Z}_n$.

**Principle 2.1** （反证法，略）

**Theorem 2.7** If an element of $\mathbb{Z}_n$ has a multiplicative inverse, then it has exactly one inverse.

**Lemma 2.8** The equation
$$a \cdot_n x = 1$$
has a solution in $\mathbb{Z}_n$ if and only if there exist integers $x$ and $y$ such that
$$ax + ny = 1.$$

**Theorem 2.9** A number $a$ has a multiplicative inverse in $\mathbb{Z}_n$ if and only if there are integers $x$ and $y$ such that $ax + ny = 1$.

**Corollary 2.10** If $a \in \mathbb{Z}_n$ and $x$ and $y$ are integers such that $ax + ny = 1$, then the multiplicative inverse of $a$ in $\mathbb{Z_n}$ is $x \mod n$.

**Lemma 2.11** Given $a$ and $n$, if there exist integers $x$ and $y$ such that $ax + ny = 1$, then $\gcd(a, n) = 1$. That is, $a$ and $n$ are relatively prime.

**Theorem 2.12 (Euclid's Division Theorem, Restricted Version)** Let $n$ be a positive integer. Then for every nonnegative integer $m$, there exist unique integers $q$ and $r$ such that $m = nq + r$ and $0 \leqslant r < n$.

**Lemma 2.13** If $j, k, q$ and $r$ are positive integers such that $k = jq + r$, then
$$\gcd(j, k) = \gcd(r, j).$$

GCD与exGCD算法（略）

**Theorem 2.14** Given two integers $j$ and $k$, Euclid's extended GCD algorithm computes $\gcd(j, k)$ and two integers $x$ and $y$ such that $\gcd(j, k) = jx + ky$.

**Theorem 2.15** Two positive integers $j$ and $k$ have greatest common divisor 1 (and thus are relatively prime) if and only if there are integers $x$ and $y$ such that $jx + ky = 1$.

**Corollary 2.16** For any positive integer $n$, an element $a$ of $\mathbb{Z}_n$ has a multiplicative inverse if and only if $\gcd(a, n) = 1$.

**Corollary 2.17** For any prime $p$, every nonzero element $a$ of $\mathbb{Z}_p$ has an inverse.