Summary of Lecture 7

L07 – Prime number theorem, Fermat test, linear congruence equations, and system of linear congruences

2026年3月25日

213.5K

Chebyshev’s theta function: $\theta(x) = \sum_{p \le x} \ln p$

THEOREM:$\theta(x) = \Theta(\pi(x) \ln x)$.

THEOREM: For any real number $x \ge 1$, $\theta(x) < (2 \ln 2)x$.

THEOREM (Hadamard; Poussin, 1896):$\lim_{x \to \infty} \frac{\pi(x)}{\frac{x}{\ln x}} = 1$

• $\pi(x) > \frac{x}{\ln x}\left(1 + \frac{1}{2\ln x}\right), x \ge 59$; $\pi(x) < \frac{x}{\ln x}\left(1 + \frac{3}{2\ln x}\right), x > 1$
  // Rosser and Schoenfeld

THEOREM:$|\mathbb{P}_n| \ge \frac{2^n}{n \ln 2}\left(\frac{1}{2} + O\left(\frac{1}{n}\right)\right)$ when $n \to \infty$.

Prime Number Generation: choose and test // at most $2n \ln 2$ trials

• Fermat test: $\textbf{Fermat}(n, t)$

THEOREM: Let $n \in \mathbb{Z}^+, a, b \in \mathbb{Z}, \gcd(a, n) = d$ and $t = \left(\frac{a}{d}\right)^{-1} \bmod \frac{n}{d}$. If $d \mid b$, then $ax \equiv b \pmod{n}$ if and only if $x \equiv \frac{b}{d}t \pmod{\frac{n}{d}}$.

Chinese Remainder Theorem

THEROEM: Let $n_1, \dots, n_k \in \mathbb{Z}^+$ be pairwise relatively prime and let $n = n_1 \cdots n_k$. Then for any $b_1, \dots, b_k \in \mathbb{Z}$, then the system

always has a solution. Furthermore, if $b \in \mathbb{Z}$ is a solution, then any solution $x$ must satisfy $x \equiv b \pmod n$.

Solution to Sun-Tsu’s Question

EXAMPLE: Solve the system $\begin{cases}x\equiv 2\pmod{3}\\x\equiv 3\pmod{5}\\x\equiv 2\pmod{7}\end{cases}$.

• $n_1 = 3, n_2 = 5, n_3 = 7; n = n_1 n_2 n_3 = 105; b_1 = 2, b_2 = 3, b_3 = 2$
  • $N_1 = n_2 n_3 = 35, N_2 = n_1 n_3 = 21, N_3 = n_1 n_2 = 15$
  • $12 n_1 – N_1 = 1; -4 n_2 + N_2 = 1; -2 n_3 + N_3 = 1$
  • $t_1 = 12, s_1 = -1; t_2 = -4, s_2 = 1; t_3 = -2, s_3 = 1$
• $b = b_1(N_1 s_1) + b_2(N_2 s_2) + b_3(N_3 s_3)$
  $= 2 (-35) + 3 (21) + 2(15)$
  $= 23$
• $x \in \mathbb{Z}$ is a solution of the system iff $x \equiv 23 \pmod{105}$
• Solutions: $[23]_{105}$

CRT Map

THEOREM: Let $n_1, \dots, n_k \in \mathbb{Z}^+$ and $\gcd(n_i, n_j) = 1$ for all $i \neq j$. Let $n = n_1 \cdots n_k$. The CRT map $\theta([x]_n) = ([x]_{n_1}, \dots, [x]_{n_k})$ is a bijection from $\mathbb{Z}_n^*$ to $\mathbb{Z}_{n_1}^*\times \cdots \times \mathbb{Z}_{n_k}^*$.

• $\theta$ is well-defined:
  • show that $\theta([x]n) \in \mathbb{Z}{n_1}^* \times \cdots \times \mathbb{Z}_{n_k}^*$ for every $[x]_n \in \mathbb{Z}_n^*$
    • $[x]_n \in \mathbb{Z}_n^* \implies \gcd(x, n) = 1 \implies \gcd(x, n_i) = 1$ for every $i \in [k] \implies [x]_{n_i} \in \mathbb{Z}_{n_i}^*$ for every $i \in [k]$
  • show that $[x]_n = [y]_n \implies \theta([x]_n) = \theta([y]_n)$
    • $[x]_n = [y]_n \implies x \equiv y \pmod{n} \implies x \equiv y \pmod{n_i}$ for every $i \in [k]$;
      $\implies [x]_{n_i} = [y]_{n_i}$ for every $i \in [k]$
      $\implies \theta([x]_n) = \theta([y]_n)$
• $\theta$ is injective, i.e., $\theta([x]_n) = \theta([y]_n) \implies [x]_n = [y]_n$
  • $\theta([x]_n) = \theta([y]_n) \implies ([x]_{n_1}, \dots, [x]_{n_k}) = ([y]_{n_1}, \dots, [y]_{n_k}) \implies [x]_{n_i} = [y]_{n_i}$ for every $i \in [k]$
    $\implies n_i \mid (x – y)$ for every $i \in [k]$
    $\implies n \mid (x – y) \implies [x]_n = [y]_n$
• $\theta$ is surjective: Let $([b_1]_{n_1}, \dots, [b_k]_{n_k}) \in \mathbb{Z}_{n_1}^* \times \cdots \times \mathbb{Z}_{n_k}^*$. Preimage?
  • Due to CRT, the system $x \equiv b_i \pmod{n_i}, i = 1, \dots, k$, has a solution $b$
  • $b \equiv b_i \pmod{n_i}$ for all $i \in [k]$
  • Since $[b_i]_{n_i} \in \mathbb{Z}_{n_i}^*$, $\gcd(b, n_i) = 1$ for all $i \in [k]$
  • $\gcd(b, n_1 n_2 \cdots n_k) = 1$
  • $\theta([b]_n) = ([b]_{n_1}, \dots, [b]_{n_k}) = ([b_1]_{n_1}, \dots, [b_k]_{n_k})$
  • $[b]_n$ is a preimage of $([b_1]_{n_1}, \dots, [b_k]_{n_k})$

Euler’s Phi Function

THEOREM: Let $n_1, \dots, n_k \in \mathbb{Z}^+$ be pairwise relatively prime. Let $n = n_1 \cdots n_k$. Then $\phi(n) = \phi(n_1) \cdots \phi(n_k)$.

• $\theta: \mathbb{Z}_n^* \to \mathbb{Z}_{n_1}^* \times \cdots \times \mathbb{Z}_{n_k}^*$ is bijective
• $\phi(n) = \phi(n_1) \times \cdots \times \phi(n_k)$

THEOREM: If $n = p_1^{e_1} \cdots p_k^{e_k}$ for distinct primes $p_1, \dots, p_k$ and integers $e_1, \dots, e_k \ge 1$, then $\phi(n) = n(1 – p_1^{-1}) \cdots (1 – p_k^{-1})$.

• $\phi(n) = \phi(p_1^{e_1}) \cdots \phi(p_k^{e_k}) = n(1 – p_1^{-1}) \cdots (1 – p_k^{-1})$

EXAMPLE:$\phi(10) = \phi(2)\phi(5) = 4$; $n = 10; n_1 = 2, n_2 = 5$

• $\theta: \mathbb{Z}_n^* \to \mathbb{Z}_{n_1}^* \times \mathbb{Z}_{n_2}^*$
  $1 \mapsto (1,1); 3 \mapsto (1,3); 7 \mapsto (1,2); 9 \mapsto (1,4)$

$(\mathbb{Z}_n, +)$

EXAMPLE: For $n \in \mathbb{Z}^+$, $\mathbb{Z}_n$ and $+$ satisfy the following properties.

• Closure:$[a]_n + [b]_n \in \mathbb{Z}_n$
  • $[a]_n + [b]_n = [a + b]_n \in \mathbb{Z}_n$
• Associative:$([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)$
  • $([a]_n + [b]_n) + [c]_n = [a + b]_n + [c]_n = [(a + b) + c]_n$
    $= [a + (b + c)]_n = [a]_n + [b + c]_n$
    $= [a]_n + ([b]_n + [c]_n)$
• Identity:$[a]_n + [0]_n = [0]_n + [a]_n = [a]_n$
  • $[a]_n + [0]_n = [a + 0]_n = [0 + a]_n = [0]_n + [a]_n$
• Inverse:$[a]_n + [-a]_n = [-a]_n + [a]_n = [0]_n$
  • $[a]_n + [-a]_n = [a + (-a)]_n = [0]_n$
• Commutative:$[a]_n + [b]_n = [b]_n + [a]_n$
  • $[a]_n + [b]_n = [a + b]_n = [b + a]_n = [b]_n + [a]_n$

Group

DEFINITION: A group is a set $G$ together with a binary operation $\star$ on $G$ such that

• Closure:$\forall a, b \in G, a \star b \in G$
• Associative:$\forall a, b, c \in G, a \star (b \star c) = (a \star b) \star c$
• Identity:$\exists e \in G, \forall a \in G, a \star e = e \star a = a$
• Inverse:$\forall a \in G, \exists b \in G, a \star b = b \star a = e$

DEFINITION: A group $G$ is said to be an Abelian group if it is

• Commutative:$\forall a, b \in G, a \star b = b \star a$

Group $\mathbb{Z}_n^*$

THEOREM:$\mathbb{Z}_n^*$ is an Abelian group for any integer $n > 1$.

• Closure:$\forall [a]_n, [b]_n \in \mathbb{Z}_n^*, [a]_n \cdot [b]_n = [ab]_n \in \mathbb{Z}_n^*$
• Associative:$\forall [a]_n, [b]_n, [c]_n \in \mathbb{Z}_n^*, [a]_n \cdot ([b]_n \cdot [c]_n) = [abc]_n = ([a]_n \cdot [b]_n) \cdot [c]_n$
• Identity element:$\exists [1]_n \in \mathbb{Z}_n^, \forall [a]_n \in \mathbb{Z}_n^, [a]_n \cdot [1]_n = [1]_n \cdot [a]_n = [a]_n$
• Inverse:$\forall [a]_n \in \mathbb{Z}_n^*, \exists [s]_n \in \mathbb{Z}_n^*$ such that $[a]_n \cdot [s]_n = [s]_n \cdot [a]_n = [1]_n$
• Commutative:$\forall [a]_n, [b]_n \in \mathbb{Z}_n^*, [a]_n \cdot [b]_n = [ab]_n = [ba]_n = [b]_n \cdot [a]_n$

REMARK: we are interested in two types of Abelian groups

• Additive Group: binary operation $+$; identity $0$
  • Example: $(\mathbb{Z}, +), (n\mathbb{Z}, +), (\mathbb{Q}, +), (\mathbb{Z}_n, +)$
• Multiplicative Group: binary operation $\cdot$; identity $1$ //$(\mathbb{Z}_n^*, \cdot)$
  • Example: $(\mathbb{Q}^*, \times), ({\pm 1}, \times), (\mathbb{Z}_n^*, \cdot)$

Order

DEFINITION: The order of a group $G$ is the cardinality of $G$.

• $|\mathbb{Z}_n| = n, |\mathbb{Z}_p^*| = p – 1, |\mathbb{Z}| = \infty$

DEFINITION: when $|G| < \infty$, $\forall a \in G$, the order of $a$ is the least integer $l > 0$ such that $a^l = 1$ ($la = 0$ for additive group)

EXAMPLE: Determine the orders of all elements of $\mathbb{Z}_7^*$ and $\mathbb{Z}_6$

• $\mathbb{Z}_7^* = \{1,2,3,4,5,6\}; o(1) = 1; o(2) = o(4) = 3; o(3) = o(5) = 6; o(6) = 2$
• $\mathbb{Z}_6 = \{0,1,2,3,4,5\}; o(0) = 1, o(1) = o(5) = 6, o(2) = o(4) = 3, o(3) = 2$

THEOREM: Let $G$ be a multiplicative Abelian group of order $m$. Then for any $a \in G$, $a^m = 1$.

• $G = \{a_1, \dots, a_m\}$
• If $i \neq j$, then $aa_i \neq aa_j$.
• $aa_1 \cdot aa_2 \cdots aa_m = a_1 a_2 \cdots a_m$
• $a^m = 1$