# 问题求解4-6 数论初步

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