Summary of Lecture 6

L06 – EA, EEA, and Chebyshev’s Theorem

2026年3月21日

5611.6K

$\mathbf{EEA}(a, b)$: input$a, b\,(a \ge b > 0)$; output$d = \gcd(a, b)$, integers $s, t$ such that $d = as + bt$

• $r_0 = a; r_1 = b; \begin{pmatrix} s_0 \\ t_0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}; \begin{pmatrix} s_1 \\ t_1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix};$
• $r_0 = r_1q_1 + r_2\,(0 < r_2 < r_1); \begin{pmatrix} s_2 \\ t_2 \end{pmatrix} = \begin{pmatrix} s_0 \\ t_0 \end{pmatrix} – q_1 \begin{pmatrix} s_1 \\ t_1 \end{pmatrix}$
• $\vdots$
• $r_{i-1} = r_iq_i + r_{i+1}\,(0 < r_{i+1} < r_i); \begin{pmatrix} s_{i+1} \\ t_{i+1} \end{pmatrix} = \begin{pmatrix} s_{i-1} \\ t_{i-1} \end{pmatrix} – q_i \begin{pmatrix} s_i \\ t_i \end{pmatrix}$
• $\vdots$
• $r_{k-2} = r_{k-1}q_{k-1} + r_k\,(0 < r_k < r_{k-1}); \begin{pmatrix} s_k \\ t_k \end{pmatrix} = \begin{pmatrix} s_{k-2} \\ t_{k-2} \end{pmatrix} – q_{k-1} \begin{pmatrix} s_{k-1} \\ t_{k-1} \end{pmatrix}$
• $r_{k-1} = r_kq_k$
• output $r_k, s_k, t_k$

$O(\ell(a)\ell(b))$ bit operations

Notations:$\Omega, \Theta, \pi(x) = \sum_{p \le x} 1, v_p(n)$
// $p^{v_p(n)} | n, p^{v_p(n)+1} \nmid n$

THEOREM (Chebyshev, 1850)$\pi(x) = \Theta\left(\frac{x}{\ln x}\right)$.

LEMMA: Suppose that $m \in \mathbb{Z}^+$. Then

LEMMA: Suppose that $p$ is a prime and $n \in \mathbb{Z}^+$. Then

THEOREM: Let $n \in \mathbb{Z}^+$ and $n \ge 2$. Then $\pi(n) \ge \frac{\ln 2}{2} \cdot \frac{n}{\ln n}$.

COROLLARY:$\pi(x) = \Omega\left(\frac{x}{\ln x}\right)$.
// $\pi(x) \ge \frac{\ln 2}{4} \cdot \frac{x}{\ln x}$

Chebyshev’s Theorem

COROLLARY:$\pi(x) = \Omega\left(\frac{x}{\ln x}\right)$.

• For any real number $x \ge 2$, we have $\pi(x) \ge \pi(\lfloor x \rfloor) \ge \frac{\ln 2}{2} \cdot \frac{\lfloor x \rfloor}{\ln \lfloor x \rfloor} \ge \frac{\ln 2}{2} \cdot \frac{x-1}{\ln x} \ge \frac{\ln 2}{4} \cdot \frac{x}{\ln x}$

Chebyshev’s theta function:$\theta(x) = \sum_{p \le x} \ln p$
// $\theta(5.2) = \ln 2 + \ln 3 + \ln 5 = \ln 30$

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

• $\theta(x) \le \pi(x) \cdot \ln x$
  // there are $\pi(x)$ terms in $\theta(x)$, each of which is $\le \ln x$
• $\theta(x) \ge \sum_{\sqrt{x} < p \le x} \ln p$
  $\ge (\pi(x) – \sqrt{x}) \ln \sqrt{x}$
  // there are at least $\pi(x) – \sqrt{x}$ terms in the sum $\sum_{\sqrt{x} < p \le x} \ln p$, each $\ge \ln \sqrt{x}$
  $= \frac{1}{2} \left( 1 – \frac{\sqrt{x}}{\pi(x)} \right) \pi(x) \ln x$
  • $\pi(x) \ge \frac{\ln 2}{4} \cdot \frac{x}{\ln x} \Rightarrow \frac{\sqrt{x}}{\pi(x)} \le \frac{4 \ln x}{\sqrt{x} \ln 2} \to 0$ (when $x \to \infty$)
  • $\frac{\sqrt{x}}{\pi(x)} < \frac{1}{2}$ when $x$ is big enough, say $x \ge x_0$
  • $\theta(x) \ge \frac{1}{4} \pi(x) \ln x$ for $x \ge x_0$

THEOREM: For any integer $n \ge 1, \theta(n) < (2 \ln 2)n$.

• $n = 1: \theta(1) = 0 < (2 \ln 2) \cdot 1$
• $n = 2: \theta(2) = \ln 2 < (2 \ln 2) \cdot 2$
• $n = 3: \theta(3) = \ln 2 + \ln 3 < (2 \ln 2) \cdot 3$ // $\ln 6 < \ln 2^6$
• $n > 3$ and $2|n$: $\theta(n) = \theta(n-1) < (2 \ln 2)(n-1) < (2 \ln 2)n$
• $n > 3$ and $2 \nmid n$: there is an integer $m \ge 2$ such that $n = 2m + 1$
  • $M = \binom{2m+1}{m} = \frac{(2m+1)\cdots(m+2)}{m!} < 2^{2m}$
  • Any prime $p, m+1 < p \le 2m+1$ must divide $M$
  • $\theta(2m+1) – \theta(m+1) = \sum_{m+1 < p \le 2m+1} \ln p$
    $\le \ln M$
    $< (2 \ln 2)m$
  • $\theta(n) = \theta(2m+1) – \theta(m+1) + \theta(m+1)$
    $< (2 \ln 2)m + (2 \ln 2)(m+1)$
    $= (2 \ln 2)n$

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

Prime Number Theorem

DEFINITION: For $x \in \mathbb{R}^+$, $\pi(x) = \sum_{p \le x} 1$: $\#$ of primes $\le x$

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

• Conjectured by Legendre and Gauss (1777-1855) in 1791, proved independently by Hadamard (1865-1963) and de la Vallée Poussin (1866-1962) in 1896
• Chebyshev: if the limit exists, then it is equal to $1$
• Rosser (1907-1989) and Schoenfeld (1920-2002) proved in 1962:
  • $\pi(x) > \frac{x}{\ln x} (1 + \frac{1}{2 \ln x})$ when $x \ge 59$
  • $\pi(x) < \frac{x}{\ln x} (1 + \frac{3}{2 \ln x})$ when $x > 1$

NOTATION:$\mathbb{P}$ – the set of all primes; $\mathbb{P}_n = \{p \in \mathbb{P} : 2^{n-1} \le p < 2^n\}$.

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

EXAMPLE: The number of $n$-bit primes for $n \in \{10, …, 25\}$.

Prime Number Generation

Basic Idea: randomly choose $n$-bit integers until a prime found.

• The number of $n$-bit integers is $2^{n-1}$
• $|\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$
• The probability that a prime is chosen in every trial is equal to
  $\alpha_n = \frac{1}{n \ln 2} \left(1 + O\left(\frac{1}{n}\right)\right), n \to \infty$
• In $\alpha_n^{-1} = \frac{n \ln 2}{1 + O\left(\frac{1}{n}\right)} \le 2n \ln 2$ trials, we get a prime.

Efficient Algorithms: An algorithm is considered as efficient if its (expected) running time is a polynomial in the bit length of its input.
//a.k.a. (expected) polynomial-time algorithm

Expected complexity: Choosing an $n$-bit prime can be done efficiently.

• The expected $\#$ of trials is $\le 2n \ln 2$, a polynomial in $n$ (input length)
• Determine if an $n$-bit integer is prime can be done efficiently

THEOREM: An integer $n \ge 1$ is a prime iff $a^{n-1} \equiv 1 \pmod{n}$ for $a = 1, 2, \dots, n-1$.

• $\implies$: by Fermat’s little theorem
• $\implies$: if not, then $n = kl$. We cannot have $k^{n-1} \equiv 1 \pmod{n}$

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

• Input: an odd integer $n \ge 3$ and an integer $t \ge 1$
• Output: prime/composite
  • for $i = 1$ to $t$ do
    • choose a random integer $a \in \{2, \dots, n-2\}$
    • If $(a^{n-1}\bmod n) \neq 1$
      • return “composite”
  • return “prime”
• Analysis:
  • If $n$ is a prime, always output “prime”
  • If $n$ is a composite, may output “prime” or “composite”
    // may fail with large probability for certain numbers

Other test algorithms: Solovay-Strassen, Miller-Rabin, Agrawal-Kayal-Saxena (2002)

Linear Congruence Equations

DEFINITION: Let $a, b \in \mathbb{Z}, n \in \mathbb{Z}^+$. A linear congruence equation is a congruence of the form $ax \equiv b \pmod n$, where $x$ is unknown.

THEOREM: Let $n \in \mathbb{Z}^+, a \in \mathbb{Z}$ and $d = \gcd(a, n)$. Then $ax \equiv b \pmod n$ has a solution if and only if $d\mid b$.

• $\implies$: suppose that $ax_0 \equiv b \pmod n$ for a specific $x_0 \in \mathbb{Z}$
  • $\exists z \in \mathbb{Z}$ such that $ax_0 – b = nz$
  • $b = ax_0 – nz$
  • $d\mid a, d\mid n \implies d\mid b$
• $\impliedby$: suppose that $d\mid b$
  • $d = \gcd(a, n)$
    • $\exists s, t \in \mathbb{Z}$ such that $as + nt = d$
    • $b = dz = asz + ntz$
    • $a(sz) \equiv b \pmod n$
    • $sz$ is a solution

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

System of Linear Congruences

Sun-Tsu’s Question: There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What will be the number of things?

• $x \equiv 2 \pmod{3}$;
• $x \equiv 3 \pmod{5}$;
• $x \equiv 2 \pmod{7}$

DEFINITION: A system of linear congruences is a set of linear congruence equations of the form

• $x \in \mathbb{Z}$ is a solution if it satisfies all $k$ equations.