数论：整数世界的法则与秩序

数论：整数世界的法则与秩序

数论是研究整数性质的数学分支，被誉为“数学的皇后”。它的魅力在于简单问题的深刻解答——从小学的质数概念，到现代密码学的基础，数论始终保持着一种纯粹而强大的美感。

一、基础基石：整除与算术基本定理

1.1 带余除法——整数的基本事实

定理：对任意整数a aa和正整数b bb，存在唯一的整数对( q , r ) (q, r)(q,r)使得：
a = b q + r , 0 ≤ r < b a = bq + r, \quad 0 \le r < ba=bq+r,0≤r<b

证明：

• 存在性：考虑集合S = { a − b k ∣ k ∈ Z , a − b k ≥ 0 } S = \{ a - bk \mid k \in \mathbb{Z}, a - bk \ge 0 \}S={a−bk∣k∈Z,a−bk≥0}

  • 首先证明S SS非空：若a ≥ 0 a \ge 0a≥0，取k = 0 k=0k=0得a ∈ S a \in Sa∈S；若a < 0 a < 0a<0，取k = a k=ak=a得a − b a = a ( 1 − b ) ≥ 0 a - ba = a(1-b) \ge 0a−ba=a(1−b)≥0（因b ≥ 1 b \ge 1b≥1）
  • 由良序原理（每个非空非负整数集有最小元），S SS有最小元，记为r rr
  • 令q qq为对应的k kk值，即r = a − b q r = a - bqr=a−bq
  • 证明0 ≤ r < b 0 \le r < b0≤r<b：
    • 显然r ≥ 0 r \ge 0r≥0（由S SS定义）
    • 若r ≥ b r \ge br≥b，则r − b = a − b ( q + 1 ) ≥ 0 r - b = a - b(q+1) \ge 0r−b=a−b(q+1)≥0且r − b < r r-b < rr−b<r，这与r rr是S SS中最小元矛盾

• 唯一性：
  假设有两组解( q 1 , r 1 ) , ( q 2 , r 2 ) (q_1, r_1), (q_2, r_2)(q1​,r1​),(q2​,r2​)，则：
  b q 1 + r 1 = b q 2 + r 2 bq_1 + r_1 = bq_2 + r_2bq1​+r1​=bq2​+r2​
  b ( q 1 − q 2 ) = r 2 − r 1 b(q_1 - q_2) = r_2 - r_1b(q1​−q2​)=r2​−r1​
  左边是b bb的倍数，右边绝对值小于b bb，只能都为 0，故q 1 = q 2 , r 1 = r 2 q_1 = q_2, r_1 = r_2q1​=q2​,r1​=r2​。

应用：

• 模运算的定义基础
• 计算机中的取模操作原理
• 进制转换的理论依据

1.2 算术基本定理——整数的"基因编码"

定理：每个大于1的整数可唯一地表示为素数的乘积（不计顺序）。

证明：
第一部分：存在性（数学归纳法）

1. 基础：n = 2 n=2n=2是素数，成立
2. 归纳假设：假设所有小于n nn的整数都有素数分解
3. 若n nn是素数，分解为自身
4. 若n nn是合数，则n = a b n = abn=ab，其中1 < a , b < n 1 < a, b < n1<a,b<n
5. 由归纳假设，a , b a, ba,b各有素数分解，相乘即得n nn的分解

第二部分：唯一性（关键引理：欧几里得引理）

• 欧几里得引理：若素数p ∣ a b p \mid abp∣ab，则p ∣ a p \mid ap∣a或p ∣ b p \mid bp∣b
• 证明：设p ∤ a p \nmid ap∤a，则gcd ⁡ ( p , a ) = 1 \gcd(p, a) = 1gcd(p,a)=1，由贝祖定理存在x , y x,yx,y使p x + a y = 1 px + ay = 1px+ay=1，两边乘b bb得p b x + a b y = b pbx + aby = bpbx+aby=b，由于p ∣ a b p \mid abp∣ab，故p ∣ b p \mid bp∣b

唯一性证明：
假设n = p 1 p 2 ⋯ p k = q 1 q 2 ⋯ q m n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_mn=p1​p2​⋯pk​=q1​q2​⋯qm​
由欧几里得引理，p 1 p_1p1​必整除某个q j q_jqj​，由于都是素数，p 1 = q j p_1 = q_jp1​=qj​
约去p 1 p_1p1​后对更小的数归纳，可得唯一性。

应用：

• 最大公因数和最小公倍数的计算
• 约数个数的公式：若n = p 1 a 1 ⋯ p k a k n = p_1^{a_1} \cdots p_k^{a_k}n=p1a1​​⋯pkak​​，则约数个数d ( n ) = ( a 1 + 1 ) ( a 2 + 1 ) ⋯ ( a k + 1 ) d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)d(n)=(a1​+1)(a2​+1)⋯(ak​+1)
• RSA密码系统的安全性基础

二、最大公因数与线性方程

2.1 欧几里得算法——最古老的算法

算法步骤：
对于a , b a, ba,b（设a ≥ b > 0 a \ge b > 0a≥b>0）：

1. 计算a = b q 1 + r 1 a = bq_1 + r_1a=bq1​+r1​，0 ≤ r 1 < b 0 \le r_1 < b0≤r1​<b
2. 若r 1 = 0 r_1 = 0r1​=0，则gcd ⁡ ( a , b ) = b \gcd(a,b) = bgcd(a,b)=b
3. 否则，令a = b , b = r 1 a = b, b = r_1a=b,b=r1​，重复步骤

原理：gcd ⁡ ( a , b ) = gcd ⁡ ( b , a m o d b ) \gcd(a,b) = \gcd(b, a \bmod b)gcd(a,b)=gcd(b,amodb)

证明：
设d = gcd ⁡ ( a , b ) d = \gcd(a,b)d=gcd(a,b)，则d ∣ a , d ∣ b d \mid a, d \mid bd∣a,d∣b
由a = b q + r a = bq + ra=bq+r得r = a − b q r = a - bqr=a−bq，故d ∣ r d \mid rd∣r
所以d dd是b bb和r rr的公因数。

反之，若d ′ = gcd ⁡ ( b , r ) d' = \gcd(b, r)d′=gcd(b,r)，则d ′ ∣ b , d ′ ∣ r d' \mid b, d' \mid rd′∣b,d′∣r
由a = b q + r a = bq + ra=bq+r得d ′ ∣ a d' \mid ad′∣a，故d ′ d'd′是a , b a,ba,b的公因数。

因此两边的最大公因数相同。

时间复杂度：O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a,b))O(logmin(a,b))，惊人地高效！

应用：

• 分数化简：12 18 = 12 / gcd ⁡ ( 12 , 18 ) 18 / gcd ⁡ ( 12 , 18 ) = 2 3 \frac{12}{18} = \frac{12/\gcd(12,18)}{18/\gcd(12,18)} = \frac{2}{3}1812​=18/gcd(12,18)12/gcd(12,18)​=32​
• 判断两数是否互质

2.2 贝祖定理（裴蜀定理）——线性组合的魔力

定理：对任意整数a , b a,ba,b，存在整数x , y x,yx,y使得：
a x + b y = gcd ⁡ ( a , b ) ax + by = \gcd(a,b)ax+by=gcd(a,b)

证明（构造性）：
考虑集合S = { a x + b y ∣ x , y ∈ Z , a x + b y > 0 } S = \{ax + by \mid x,y \in \mathbb{Z}, ax+by > 0\}S={ax+by∣x,y∈Z,ax+by>0}

1. S SS非空（取适当x , y x,yx,y可得正数）
2. 由良序原理，S SS有最小元d = a x 0 + b y 0 d = ax_0 + by_0d=ax0​+by0​
3. 证明d ∣ a d \mid ad∣a：
   用带余除法：a = d q + r a = dq + ra=dq+r，0 ≤ r < d 0 \le r < d0≤r<d
   则r = a − d q = a − ( a x 0 + b y 0 ) q = a ( 1 − x 0 q ) + b ( − y 0 q ) r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0q) + b(-y_0q)r=a−dq=a−(ax0​+by0​)q=a(1−x0​q)+b(−y0​q)
   若r > 0 r > 0r>0，则r ∈ S r \in Sr∈S且r < d r < dr<d，与d dd最小矛盾，故r = 0 r=0r=0，即d ∣ a d \mid ad∣a
4. 同理d ∣ b d \mid bd∣b，故d dd是a , b a,ba,b的公因数
5. 任何公因数c cc都整除d = a x 0 + b y 0 d = ax_0 + by_0d=ax0​+by0​，故d dd是最大公因数

扩展欧几里得算法：
在欧几里得算法过程中，反向递推可求得x , y x,yx,y
若a = b q + r a = bq + ra=bq+r，且已知b x ′ + r y ′ = gcd ⁡ ( b , r ) = d bx' + ry' = \gcd(b,r) = dbx′+ry′=gcd(b,r)=d
则d = b x ′ + ( a − b q ) y ′ = a y ′ + b ( x ′ − q y ′ ) d = bx' + (a - bq)y' = ay' + b(x' - qy')d=bx′+(a−bq)y′=ay′+b(x′−qy′)

应用：

• 线性丢番图方程a x + b y = c ax + by = cax+by=c有解 ⇔gcd ⁡ ( a , b ) ∣ c \gcd(a,b) \mid cgcd(a,b)∣c
• 模逆元的计算（密码学核心）
• 证明：若gcd ⁡ ( a , b ) = 1 \gcd(a,b)=1gcd(a,b)=1且a ∣ b c a \mid bca∣bc，则a ∣ c a \mid ca∣c（因为存在x , y x,yx,y使a x + b y = 1 ax+by=1ax+by=1，乘c cc得a c x + b c y = c acx + bcy = cacx+bcy=c）

三、同余理论——时钟算术

3.1 同余的基本性质

定义：a ≡ b ( m o d m ) a \equiv b \pmod{m}a≡b(modm)⇔m ∣ ( a − b ) m \mid (a-b)m∣(a−b)

性质：

1. 等价关系：自反、对称、传递
2. 运算保持：
   • 若a ≡ b , c ≡ d a \equiv b, c \equiv da≡b,c≡d，则a ± c ≡ b ± d a \pm c \equiv b \pm da±c≡b±d
   • 若a ≡ b , c ≡ d a \equiv b, c \equiv da≡b,c≡d，则a c ≡ b d ac \equiv bdac≡bd
3. 幂运算：若a ≡ b a \equiv ba≡b，则a n ≡ b n a^n \equiv b^nan≡bn

小心除法：a c ≡ b c ( m o d m ) ac \equiv bc \pmod{m}ac≡bc(modm)⇒a ≡ b ( m o d m gcd ⁡ ( c , m ) ) a \equiv b \pmod{\frac{m}{\gcd(c,m)}}a≡b(modgcd(c,m)m​)

3.2 费马小定理——素数检测的曙光

定理：若p pp为素数，且p ∤ a p \nmid ap∤a，则：
a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)

证明（组合证明，优美！）：
考虑数列a , 2 a , 3 a , … , ( p − 1 ) a ( m o d p ) a, 2a, 3a, \ldots, (p-1)a \pmod{p}a,2a,3a,…,(p−1)a(modp)

• 它们模p pp两两不同余：若i a ≡ j a ( m o d p ) ia \equiv ja \pmod{p}ia≡ja(modp)，则p ∣ a ( i − j ) p \mid a(i-j)p∣a(i−j)，因p ∤ a p \nmid ap∤a，故p ∣ ( i − j ) p \mid (i-j)p∣(i−j)，但∣ i − j ∣ < p \lvert i-j \rvert < p∣i−j∣<p，只能i = j i=ji=j
• 因此这p − 1 p-1p−1个数恰好是1 , 2 , … , p − 1 1,2,\ldots,p-11,2,…,p−1的一个排列
• 相乘：a ⋅ 2 a ⋅ 3 a ⋯ ( p − 1 ) a ≡ 1 ⋅ 2 ⋅ 3 ⋯ ( p − 1 ) ( m o d p ) a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}a⋅2a⋅3a⋯(p−1)a≡1⋅2⋅3⋯(p−1)(modp)
• 即a p − 1 ( p − 1 ) ! ≡ ( p − 1 ) ! ( m o d p ) a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}ap−1(p−1)!≡(p−1)!(modp)
• 由于( p − 1 ) ! (p-1)!(p−1)!与p pp互质（因p pp是素数），可约去，得证

应用：

• 费马素性测试：若a n − 1 ≢ 1 ( m o d n ) a^{n-1} \not\equiv 1 \pmod{n}an−1≡1(modn)，则n nn一定是合数（但逆命题不成立，有卡迈克尔数）
• 计算模幂：a k ( m o d p ) a^k \pmod{p}ak(modp)可简化为a k m o d ( p − 1 ) ( m o d p ) a^{k \bmod (p-1)} \pmod{p}akmod(p−1)(modp)（当p ∤ a p \nmid ap∤a）

3.3 欧拉定理——费马小定理的推广

欧拉函数φ ( n ) \varphi(n)φ(n)：小于等于n nn且与n nn互质的正整数个数

计算公式：
若n = p 1 a 1 p 2 a 2 ⋯ p k a k n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}n=p1a1​​p2a2​​⋯pkak​​，则：
φ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) ⋯ ( 1 − 1 p k ) \varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right)φ(n)=n(1−p1​1​)(1−p2​1​)⋯(1−pk​1​)

证明思路：

1. 对素数幂p a p^apa：φ ( p a ) = p a − p a − 1 = p a ( 1 − 1 / p ) \varphi(p^a) = p^a - p^{a-1} = p^a(1 - 1/p)φ(pa)=pa−pa−1=pa(1−1/p)（去掉p pp的倍数）
2. 利用中国剩余定理证明φ \varphiφ是积性函数：若gcd ⁡ ( m , n ) = 1 \gcd(m,n)=1gcd(m,n)=1，则φ ( m n ) = φ ( m ) φ ( n ) \varphi(mn)=\varphi(m)\varphi(n)φ(mn)=φ(m)φ(n)

欧拉定理：若gcd ⁡ ( a , n ) = 1 \gcd(a,n)=1gcd(a,n)=1，则：
a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)} \equiv 1 \pmod{n}aφ(n)≡1(modn)

证明（与费马小定理类似）：
设简化剩余系为{ r 1 , r 2 , … , r φ ( n ) } \{r_1, r_2, \ldots, r_{\varphi(n)}\}{r1​,r2​,…,rφ(n)​}
考虑a r 1 , a r 2 , … , a r φ ( n ) ( m o d n ) ar_1, ar_2, \ldots, ar_{\varphi(n)} \pmod{n}ar1​,ar2​,…,arφ(n)​(modn)

• 它们仍与n nn互质（因gcd ⁡ ( a , n ) = gcd ⁡ ( r i , n ) = 1 \gcd(a,n)=\gcd(r_i,n)=1gcd(a,n)=gcd(ri​,n)=1）
• 它们两两不同余（类似费马证明）
• 因此这也是一个简化剩余系
• 乘积相等：∏ a r i ≡ ∏ r i ( m o d n ) \prod ar_i \equiv \prod r_i \pmod{n}∏ari​≡∏ri​(modn)
• 即a φ ( n ) ∏ r i ≡ ∏ r i ( m o d n ) a^{\varphi(n)} \prod r_i \equiv \prod r_i \pmod{n}aφ(n)∏ri​≡∏ri​(modn)
• 因∏ r i \prod r_i∏ri​与n nn互质，可约去，得证

应用：

• RSA加密解密的核心：选择e , d e,de,d使e d ≡ 1 ( m o d φ ( N ) ) ed \equiv 1 \pmod{\varphi(N)}ed≡1(modφ(N))，则m e d ≡ m ( m o d N ) m^{ed} \equiv m \pmod{N}med≡m(modN)
• 模幂运算化简

3.4 威尔逊定理——素数的阶乘判据

定理：p pp为素数 ⇔( p − 1 ) ! ≡ − 1 ( m o d p ) (p-1)! \equiv -1 \pmod{p}(p−1)!≡−1(modp)

证明：

• 必要性（p pp是素数 ⇒ 同余成立）：
  对a = 1 , 2 , … , p − 1 a=1,2,\ldots,p-1a=1,2,…,p−1，每个a aa有唯一的乘法逆元a − 1 ( m o d p ) a^{-1} \pmod{p}a−1(modp)
  当且仅当a = a − 1 ( m o d p ) a = a^{-1} \pmod{p}a=a−1(modp)时，即a 2 ≡ 1 ( m o d p ) a^2 \equiv 1 \pmod{p}a2≡1(modp)，解得a ≡ ± 1 ( m o d p ) a \equiv \pm 1 \pmod{p}a≡±1(modp)
  因此2 , 3 , … , p − 2 2,3,\ldots,p-22,3,…,p−2可两两配对为互逆元，乘积 ≡ 1
  故( p − 1 ) ! ≡ 1 ⋅ ( p − 1 ) ≡ − 1 ( m o d p ) (p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod{p}(p−1)!≡1⋅(p−1)≡−1(modp)

• 充分性（同余成立 ⇒p pp是素数）：
  若p pp是合数，设d ∣ p d \mid pd∣p，1 < d < p 1 < d < p1<d<p
  则d ∣ ( p − 1 ) ! d \mid (p-1)!d∣(p−1)!且d ∣ p d \mid pd∣p，故d ∣ gcd ⁡ ( ( p − 1 ) ! , p ) = 1 d \mid \gcd((p-1)!, p) = 1d∣gcd((p−1)!,p)=1，矛盾

应用：

• 理论价值大于实用（计算阶乘太慢）
• 展示素数性质的优美对称性

四、中国剩余定理——古老的智慧

问题：求解同余方程组
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a k ( m o d m k ) \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}⎩⎨⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡ak​(modmk​)​
其中m 1 , m 2 , … , m k m_1, m_2, \ldots, m_km1​,m2​,…,mk​两两互质。

定理：上述方程组在模M = m 1 m 2 ⋯ m k M = m_1 m_2 \cdots m_kM=m1​m2​⋯mk​下有唯一解。

构造性证明：

1. 计算M i = M / m i M_i = M/m_iMi​=M/mi​
2. 求M i M_iMi​模m i m_imi​的逆元t i t_iti​（即M i t i ≡ 1 ( m o d m i ) M_i t_i \equiv 1 \pmod{m_i}Mi​ti​≡1(modmi​)，由贝祖定理保证存在，因gcd ⁡ ( M i , m i ) = 1 \gcd(M_i, m_i)=1gcd(Mi​,mi​)=1）
3. 解为：
   x ≡ a 1 M 1 t 1 + a 2 M 2 t 2 + ⋯ + a k M k t k ( m o d M ) x \equiv a_1 M_1 t_1 + a_2 M_2 t_2 + \cdots + a_k M_k t_k \pmod{M}x≡a1​M1​t1​+a2​M2​t2​+⋯+ak​Mk​tk​(modM)

验证：
对第i ii个方程，当j ≠ i j \neq ij=i时，m i ∣ M j m_i \mid M_jmi​∣Mj​，故a j M j t j ≡ 0 ( m o d m i ) a_j M_j t_j \equiv 0 \pmod{m_i}aj​Mj​tj​≡0(modmi​)
而a i M i t i ≡ a i ⋅ 1 ≡ a i ( m o d m i ) a_i M_i t_i \equiv a_i \cdot 1 \equiv a_i \pmod{m_i}ai​Mi​ti​≡ai​⋅1≡ai​(modmi​)
总和 ≡a i ( m o d m i ) a_i \pmod{m_i}ai​(modmi​)，满足！

应用：

• 大整数计算：用几个小模数分别计算，最后合成
• 密码学：RSA的加快解密（CRT模式）
• 历法计算：古代"物不知数"问题

五、二次剩余与二次互反律——高斯的明珠

5.1 二次剩余

定义：若存在x xx使x 2 ≡ a ( m o d p ) x^2 \equiv a \pmod{p}x2≡a(modp)（p pp奇素数，p ∤ a p \nmid ap∤a），则称a aa是模p pp的二次剩余，否则为二次非剩余。

性质：

• 模p pp的二次剩余恰有p − 1 2 \frac{p-1}{2}2p−1​个
• 乘积法则：
  • QR × QR = QR
  • QR × NR = NR
  • NR × NR = QR

5.2 勒让德符号

( a p ) = { 1 a 是模 p 的二次剩余 − 1 a 是模 p 的二次非剩余 0 p ∣ a \left(\frac{a}{p}\right) = \begin{cases} 1 & a \text{ 是模 } p \text{ 的二次剩余} \\ -1 & a \text{ 是模 } p \text{ 的二次非剩余} \\ 0 & p \mid a \end{cases}(pa​)=⎩⎨⎧​1−10​a是模p的二次剩余a是模p的二次非剩余p∣a​

欧拉判别准则：
( a p ) ≡ a p − 1 2 ( m o d p ) \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}(pa​)≡a2p−1​(modp)

5.3 二次互反律——数论皇冠上的明珠

定理：对相异奇素数p , q p, qp,q：
( p q ) ( q p ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}(qp​)(pq​)=(−1)2p−1​⋅2q−1​

等价的三种表述：

1. 若p ≡ q ≡ 3 ( m o d 4 ) p \equiv q \equiv 3 \pmod{4}p≡q≡3(mod4)，则( p q ) = − ( q p ) \left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)(qp​)=−(pq​)，否则相等
2. ( p q ) = ( q p ) \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)(qp​)=(pq​)除非p ≡ q ≡ 3 ( m o d 4 ) p \equiv q \equiv 3 \pmod{4}p≡q≡3(mod4)
3. ( q p ) = ( p q ) ⋅ ( − 1 ) p − 1 2 ⋅ q − 1 2 \left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) \cdot (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}(pq​)=(qp​)⋅(−1)2p−1​⋅2q−1​

高斯一生给出6种证明，第一种使用数学归纳法，其中关键引理：
高斯引理：( a p ) = ( − 1 ) μ \left(\frac{a}{p}\right) = (-1)^\mu(pa​)=(−1)μ，其中μ \muμ是集合{ a , 2 a , … , p − 1 2 a } \{a, 2a, \ldots, \frac{p-1}{2}a\}{a,2a,…,2p−1​a}模p pp后大于p / 2 p/2p/2的个数。

应用：

• 快速计算勒让德符号，判断二次剩余
• 证明：− 1 -1−1是模p pp的二次剩余 ⇔p ≡ 1 ( m o d 4 ) p \equiv 1 \pmod{4}p≡1(mod4)
• 证明：2 22是模p pp的二次剩余 ⇔p ≡ ± 1 ( m o d 8 ) p \equiv \pm 1 \pmod{8}p≡±1(mod8)

六、原根与离散对数——循环的结构

6.1 阶（次数）

定义：满足a n ≡ 1 ( m o d m ) a^n \equiv 1 \pmod{m}an≡1(modm)的最小正整数n nn称为a aa模m mm的阶，记作ord ⁡ m ( a ) \operatorname{ord}_m(a)ordm​(a)。

性质：

1. 若a k ≡ 1 ( m o d m ) a^k \equiv 1 \pmod{m}ak≡1(modm)，则ord ⁡ m ( a ) ∣ k \operatorname{ord}_m(a) \mid kordm​(a)∣k
2. ord ⁡ m ( a ) ∣ φ ( m ) \operatorname{ord}_m(a) \mid \varphi(m)ordm​(a)∣φ(m)

6.2 原根

定义：若ord ⁡ m ( g ) = φ ( m ) \operatorname{ord}_m(g) = \varphi(m)ordm​(g)=φ(m)，则g gg称为模m mm的原根。

存在性定理：模m mm有原根 ⇔m = 2 , 4 , p k , 2 p k m = 2, 4, p^k, 2p^km=2,4,pk,2pk（p pp为奇素数）

证明思路：

• 对素数p pp：利用因子计数，存在性由拉格朗日定理（多项式根的个数不超过次数）和阶的性质保证
• 对素数幂：通过"提升引理"从模p pp的原根构造模p k p^kpk的原根

性质：若原根存在，则恰有φ ( φ ( m ) ) \varphi(\varphi(m))φ(φ(m))个原根。

6.3 离散对数

若g gg是模m mm的原根，对任意与m mm互质的a aa，存在唯一k ( m o d φ ( m ) ) k \pmod{\varphi(m)}k(modφ(m))使：
g k ≡ a ( m o d m ) g^k \equiv a \pmod{m}gk≡a(modm)
称k kk为a aa以g gg为底的离散对数，记作ind ⁡ g a \operatorname{ind}_g aindg​a。

计算困难性：已知g , g k ( m o d p ) g, g^k \pmod{p}g,gk(modp)求k kk是离散对数问题，是 Diffie-Hellman 密钥交换和 ElGamal 加密等密码方案的安全基础。

七、素数分布——神秘的旋律

7.1 素数无穷多

欧几里得证明（反证法）：
假设只有有限个素数p 1 , p 2 , … , p n p_1, p_2, \ldots, p_np1​,p2​,…,pn​
考虑数N = p 1 p 2 ⋯ p n + 1 N = p_1 p_2 \cdots p_n + 1N=p1​p2​⋯pn​+1

• N NN大于所有p i p_ipi​
• N NN不被任何p i p_ipi​整除（余数均为1）
  故N NN有素因子不在列表中，矛盾。

其他证明：

• 欧拉分析证明：利用调和级数发散和欧拉乘积公式
• 拓扑证明（Furstenberg）：在整数上定义特殊拓扑，素数集为无限集

7.2 素数定理——分布的主旋律

定理：记π ( x ) \pi(x)π(x)为不超过x xx的素数个数，则：
π ( x ) ∼ x ln ⁡ x ( x → ∞ ) \pi(x) \sim \frac{x}{\ln x} \quad (x \to \infty)π(x)∼lnxx​(x→∞)
更精确地：π ( x ) ∼ Li ⁡ ( x ) = ∫ 2 x d t ln ⁡ t \pi(x) \sim \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}π(x)∼Li(x)=∫2x​lntdt​

历史：

• 高斯15岁时猜想（1792年）
• 勒让德提出近似公式（1808年）
• 切比雪夫证明：存在常数c 1 , c 2 c_1, c_2c1​,c2​使c 1 x ln ⁡ x < π ( x ) < c 2 x ln ⁡ x c_1 \frac{x}{\ln x} < \pi(x) < c_2 \frac{x}{\ln x}c1​lnxx​<π(x)<c2​lnxx​（1850年）
• 阿达马和瓦莱·普桑独立证明（1896年），使用复变函数和黎曼ζ函数
• 塞尔伯格和爱尔特希给出初等证明（1949年）

7.3 狄利克雷定理——等差数列中的素数

定理：若gcd ⁡ ( a , m ) = 1 \gcd(a,m)=1gcd(a,m)=1，则等差数列a , a + m , a + 2 m , … a, a+m, a+2m, \ldotsa,a+m,a+2m,…中有无穷多个素数。

证明思想：引入狄利克雷L函数：
L ( s , χ ) = ∑ n = 1 ∞ χ ( n ) n s L(s,\chi) = \sum_{n=1}^\infty \frac{\chi(n)}{n^s}L(s,χ)=n=1∑∞​nsχ(n)​
其中χ \chiχ是模m mm的狄利克雷特征（群同态）
关键步骤：证明L ( 1 , χ ) ≠ 0 L(1,\chi) \neq 0L(1,χ)=0对于非主特征χ \chiχ

意义：算术级数中素数分布均匀。

7.4 黎曼ζ函数与黎曼猜想

定义：对ℜ ( s ) > 1 \Re(s) > 1ℜ(s)>1，
ζ ( s ) = ∑ n = 1 ∞ 1 n s = ∏ p ( 1 − p − s ) − 1 \zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \prod_{p} \left(1 - p^{-s}\right)^{-1}ζ(s)=n=1∑∞​ns1​=p∏​(1−p−s)−1
（欧拉乘积公式，揭示与素数的联系）

解析延拓：可延拓到整个复平面（除s = 1 s=1s=1为单极点）

黎曼猜想（1859年提出）：ζ函数的所有非平凡零点实部均为1 / 2 1/21/2

已知结果：

• 无穷多个零点在临界线上（Hardy，1914）
• 至少41%的零点在临界线上（Conrey，1989）
• 验证了前1 0 13 10^{13}1013个零点都在临界线上（2010年代）

影响：若成立，可极大改进素数分布误差项：
∣ π ( x ) − Li ⁡ ( x ) ∣ < 1 8 π x ln ⁡ x ( 若RH成立 ) |\pi(x) - \operatorname{Li}(x)| < \frac{1}{8\pi} \sqrt{x} \ln x \quad (\text{若RH成立})∣π(x)−Li(x)∣<8π1​x​lnx(若RH成立)

八、不定方程——寻找整数解

8.1 线性不定方程

方程：a x + b y = c ax + by = cax+by=c

有解条件：gcd ⁡ ( a , b ) ∣ c \gcd(a,b) \mid cgcd(a,b)∣c

通解：若( x 0 , y 0 ) (x_0, y_0)(x0​,y0​)是一组特解（由扩展欧几里得算法求得），则所有解为：
{ x = x 0 + b d t y = y 0 − a d t t ∈ Z , d = gcd ⁡ ( a , b ) \begin{cases} x = x_0 + \frac{b}{d}t \\ y = y_0 - \frac{a}{d}t \end{cases} \quad t \in \mathbb{Z}, \ d = \gcd(a,b){x=x0​+db​ty=y0​−da​t​t∈Z,d=gcd(a,b)

8.2 勾股方程

方程：x 2 + y 2 = z 2 x^2 + y^2 = z^2x2+y2=z2

本原解：gcd ⁡ ( x , y , z ) = 1 \gcd(x,y,z)=1gcd(x,y,z)=1

通解公式（欧几里得公式）：
{ x = m 2 − n 2 y = 2 m n z = m 2 + n 2 \begin{cases} x = m^2 - n^2 \\ y = 2mn \\ z = m^2 + n^2 \end{cases}⎩⎨⎧​x=m2−n2y=2mnz=m2+n2​
其中m > n > 0 m > n > 0m>n>0，gcd ⁡ ( m , n ) = 1 \gcd(m,n)=1gcd(m,n)=1，m , n m,nm,n一奇一偶。

证明：方程化为( x z ) 2 + ( y z ) 2 = 1 \left(\frac{x}{z}\right)^2 + \left(\frac{y}{z}\right)^2 = 1(zx​)2+(zy​)2=1，即单位圆上的有理点，参数化得解。

8.3 佩尔方程

方程：x 2 − D y 2 = 1 x^2 - Dy^2 = 1x2−Dy2=1（D DD为正非平方整数）

关键事实：

• 有无穷多组正整数解
• 所有解由最小解生成：若( x 1 , y 1 ) (x_1, y_1)(x1​,y1​)是最小解，则：
  x n + y n D = ( x 1 + y 1 D ) n x_n + y_n\sqrt{D} = (x_1 + y_1\sqrt{D})^nxn​+yn​D​=(x1​+y1​D​)n

应用：求平方根的最佳有理逼近

8.4 费马大定理——350年的征程

定理：对n ≥ 3 n \ge 3n≥3，方程x n + y n = z n x^n + y^n = z^nxn+yn=zn无正整数解。

历史：

• 费马在书边注记（1637年）：“我发现了绝妙证明，但页边太小写不下”
• 欧拉证明n = 3 n=3n=3（1770年）
• 库默尔证明正则素数情形（1847年），引入理想数
• 最终由怀尔斯证明（1994年），使用模形式、椭圆曲线、伽罗瓦表示等现代工具

证明概要：

1. 只需证明n = 4 n=4n=4和奇素数情形
2. 关键联系：弗雷曲线y 2 = x ( x − a n ) ( x + b n ) y^2 = x(x-a^n)(x+b^n)y2=x(x−an)(x+bn)（若a n + b n = c n a^n+b^n=c^nan+bn=cn）
3. 里贝特证明：弗雷曲线不是模曲线（谷山-志村猜想）
4. 怀尔斯证明：半稳定椭圆曲线都是模曲线（从而费马方程无解）

九、超越数论——代数与分析的相遇

9.1 代数数与超越数

定义：

• 代数数：满足整系数多项式方程的复数
• 超越数：不是代数数的复数

例子：

• 代数数：2 , 1 + 5 2 \sqrt{2}, \frac{1+\sqrt{5}}{2}2​,21+5​​（黄金比例）, 所有有理数
• 超越数：π , e \pi, eπ,e（林德曼，埃尔米特证明）

9.2 林德曼-魏尔斯特拉斯定理

定理：若α 1 , … , α n \alpha_1, \ldots, \alpha_nα1​,…,αn​是互不相同的代数数，则e α 1 , … , e α n e^{\alpha_1}, \ldots, e^{\alpha_n}eα1​,…,eαn​在代数数域上线性无关。

推论：

1. e ee是超越数（取α 1 = 1 \alpha_1=1α1​=1）
2. π \piπ是超越数：若π \piπ是代数数，则i π i\piiπ也是，由定理e i π = − 1 e^{i\pi} = -1eiπ=−1与代数数线性无关矛盾

9.3 希尔伯特第七问题

问题：a b a^bab的超越性（a aa代数且不为0,1，b bb无理代数数）

格尔丰德-施耐德定理（1934年）：上述情况a b a^bab是超越数。

例子：

• 2 2 2^{\sqrt{2}}22​是超越数
• e π = ( − 1 ) − i e^\pi = (-1)^{-i}eπ=(−1)−i是超越数（格尔丰德常数）

十、现代应用——从纯理论到现实世界

10.1 密码学

RSA加密（1977年）：

1. 选择大素数p , q p,qp,q，计算N = p q N=pqN=pq，φ ( N ) = ( p − 1 ) ( q − 1 ) \varphi(N)=(p-1)(q-1)φ(N)=(p−1)(q−1)
2. 选择e ee使gcd ⁡ ( e , φ ( N ) ) = 1 \gcd(e,\varphi(N))=1gcd(e,φ(N))=1
3. 计算d dd使e d ≡ 1 ( m o d φ ( N ) ) ed \equiv 1 \pmod{\varphi(N)}ed≡1(modφ(N))
4. 公钥：( N , e ) (N,e)(N,e)，私钥：( N , d ) (N,d)(N,d)
5. 加密：c ≡ m e ( m o d N ) c \equiv m^e \pmod{N}c≡me(modN)
6. 解密：m ≡ c d ( m o d N ) m \equiv c^d \pmod{N}m≡cd(modN)

安全性：基于大数分解困难性

椭圆曲线密码：基于椭圆曲线离散对数问题，密钥更短，安全性更高

10.2 编码理论

纠错码：利用有限域上的多项式，如里德-所罗门码（CD、DVD、QR码使用）

校验和：模运算用于错误检测（ISBN、银行卡号）

10.3 计算机科学

哈希函数：利用模运算均匀分布
随机数生成：线性同余生成器x n + 1 ≡ a x n + b ( m o d m ) x_{n+1} \equiv ax_n + b \pmod{m}xn+1​≡axn​+b(modm)
算法分析：模运算的复杂度分析