企业官网建设流程全解析

wordpress可以做电影网站吗,华为网站建设方案模板,wordpress空间转移,网络营销方案策划报告数论#xff1a;整数世界的法则与秩序 数论是研究整数性质的数学分支#xff0c;被誉为“数学的皇后”。它的魅力在于简单问题的深刻解答——从小学的质数概念#xff0c;到现代密码学的基础#xff0c;数论始终保持着一种纯粹而强大的美感。 文章目录数论#xff1a;整数…数论整数世界的法则与秩序数论是研究整数性质的数学分支被誉为“数学的皇后”。它的魅力在于简单问题的深刻解答——从小学的质数概念到现代密码学的基础数论始终保持着一种纯粹而强大的美感。文章目录数论整数世界的法则与秩序一、基础基石整除与算术基本定理1.1 带余除法——整数的基本事实1.2 算术基本定理——整数的基因编码二、最大公因数与线性方程2.1 欧几里得算法——最古老的算法2.2 贝祖定理裴蜀定理——线性组合的魔力三、同余理论——时钟算术3.1 同余的基本性质3.2 费马小定理——素数检测的曙光3.3 欧拉定理——费马小定理的推广3.4 威尔逊定理——素数的阶乘判据四、中国剩余定理——古老的智慧五、二次剩余与二次互反律——高斯的明珠5.1 二次剩余5.2 勒让德符号5.3 二次互反律——数论皇冠上的明珠六、原根与离散对数——循环的结构6.1 阶次数6.2 原根6.3 离散对数七、素数分布——神秘的旋律7.1 素数无穷多7.2 素数定理——分布的主旋律7.3 狄利克雷定理——等差数列中的素数7.4 黎曼ζ函数与黎曼猜想八、不定方程——寻找整数解8.1 线性不定方程8.2 勾股方程8.3 佩尔方程8.4 费马大定理——350年的征程九、超越数论——代数与分析的相遇9.1 代数数与超越数9.2 林德曼-魏尔斯特拉斯定理9.3 希尔伯特第七问题十、现代应用——从纯理论到现实世界10.1 密码学10.2 编码理论10.3 计算机科学结语数论之美一、基础基石整除与算术基本定理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 babqr,0≤rb证明存在性考虑集合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 k0k0得a ∈ S a \in Sa∈S若a 0 a 0a0取k a kaka得a − b a a ( 1 − b ) ≥ 0 a - ba a(1-b) \ge 0a−baa(1−b)≥0因b ≥ 1 b \ge 1b≥1由良序原理每个非空非负整数集有最小元S SS有最小元记为r rr令q qq为对应的k kk值即r a − b q r a - bqra−bq证明0 ≤ r b 0 \le r b0≤rb显然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(q1) \ge 0r−ba−b(q1)≥0且r − b r r-b rr−br这与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的整数可唯一地表示为素数的乘积不计顺序。证明第一部分存在性数学归纳法基础n 2 n2n2是素数成立归纳假设假设所有小于n nn的整数都有素数分解若n nn是素数分解为自身若n nn是合数则n a b n abnab其中1 a , b n 1 a, b n1a,bn由归纳假设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 1pxay1两边乘b bb得p b x a b y b pbx aby bpbxabyb由于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_mnp1​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}np1a1​​⋯pkak​​则约数个数d ( n ) ( a 1 1 ) ( a 2 1 ) ⋯ ( a k 1 ) d(n) (a_11)(a_21)\cdots(a_k1)d(n)(a1​1)(a2​1)⋯(ak​1)RSA密码系统的安全性基础二、最大公因数与线性方程2.1 欧几里得算法——最古老的算法算法步骤对于a , b a, ba,b设a ≥ b 0 a \ge b 0a≥b0计算a b q 1 r 1 a bq_1 r_1abq1​r1​0 ≤ r 1 b 0 \le r_1 b0≤r1​b若r 1 0 r_1 0r1​0则gcd ⁡ ( a , b ) b \gcd(a,b) bgcd(a,b)b否则令a b , b r 1 a b, b r_1ab,br1​重复步骤原理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)dgcd(a,b)则d ∣ a , d ∣ b d \mid a, d \mid bd∣a,d∣b由a b q r a bq rabqr得r a − b q r a - bqra−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 rabqr得d ′ ∣ a d \mid ad′∣a故d ′ dd′是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)axbygcd(a,b)证明构造性考虑集合S { a x b y ∣ x , y ∈ Z , a x b y 0 } S \{ax by \mid x,y \in \mathbb{Z}, axby 0\}S{axby∣x,y∈Z,axby0}S SS非空取适当x , y x,yx,y可得正数由良序原理S SS有最小元d a x 0 b y 0 d ax_0 by_0dax0​by0​证明d ∣ a d \mid ad∣a用带余除法a d q r a dq radqr0 ≤ r d 0 \le r d0≤rd则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)ra−dqa−(ax0​by0​)qa(1−x0​q)b(−y0​q)若r 0 r 0r0则r ∈ S r \in Sr∈S且r d r drd与d dd最小矛盾故r 0 r0r0即d ∣ a d \mid ad∣a同理d ∣ b d \mid bd∣b故d dd是a , b a,ba,b的公因数任何公因数c cc都整除d a x 0 b y 0 d ax_0 by_0dax0​by0​故d dd是最大公因数扩展欧几里得算法在欧几里得算法过程中反向递推可求得x , y x,yx,y若a b q r a bq rabqr且已知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)dbx′(a−bq)y′ay′b(x′−qy′)应用线性丢番图方程a x b y c ax by caxbyc有解 ⇔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 axby1axby1乘c cc得a c x b c y c acx bcy cacxbcyc三、同余理论——时钟算术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)性质等价关系自反、对称、传递运算保持若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幂运算若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 ijij因此这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∤a3.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}np1a1​​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​)证明思路对素数幂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−1pa(1−1/p)去掉p pp的倍数利用中国剩余定理证明φ \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 a1,2,\ldots,p-1a1,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}aa−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∣p1 d p 1 d p1dp则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_kMm1​m2​⋯mk​下有唯一解。构造性证明计算M i M / m i M_i M/m_iMi​M/mi​求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解为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 QRQR × NR NRNR × NR QR5.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​等价的三种表述若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​)否则相等( 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)( 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)。性质若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)∣kord ⁡ 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^km2,4,pk,2pkp 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 1Np1​p2​⋯pn​1N 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, am, a2m, \ldotsa,am,a2m,…中有无穷多个素数。证明思想引入狄利克雷L函数L ( s , χ ) ∑ n 1 ∞ χ ( n ) n s L(s,\chi) \sum_{n1}^\infty \frac{\chi(n)}{n^s}L(s,χ)n1∑∞​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_{n1}^\infty \frac{1}{n^s} \prod_{p} \left(1 - p^{-s}\right)^{-1}ζ(s)n1∑∞​ns1​p∏​(1−p−s)−1欧拉乘积公式揭示与素数的联系解析延拓可延拓到整个复平面除s 1 s1s1为单极点黎曼猜想1859年提出ζ函数的所有非平凡零点实部均为1 / 2 1/21/2已知结果无穷多个零点在临界线上Hardy1914至少41%的零点在临界线上Conrey1989验证了前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 caxbyc有解条件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){xx0​db​tyy0​−da​t​t∈Z,dgcd(a,b)8.2 勾股方程方程x 2 y 2 z 2 x^2 y^2 z^2x2y2z2本原解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}⎩⎨⎧​xm2−n2y2mnzm2n2​其中m n 0 m n 0mn0gcd ⁡ ( m , n ) 1 \gcd(m,n)1gcd(m,n)1m , 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​)21即单位圆上的有理点参数化得解。8.3 佩尔方程方程x 2 − D y 2 1 x^2 - Dy^2 1x2−Dy21D 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^nxnynzn无正整数解。历史费马在书边注记1637年“我发现了绝妙证明但页边太小写不下”欧拉证明n 3 n3n31770年库默尔证明正则素数情形1847年引入理想数最终由怀尔斯证明1994年使用模形式、椭圆曲线、伽罗瓦表示等现代工具证明概要只需证明n 4 n4n4和奇素数情形关键联系弗雷曲线y 2 x ( x − a n ) ( x b n ) y^2 x(x-a^n)(xb^n)y2x(x−an)(xbn)若a n b n c n a^nb^nc^nanbncn里贝特证明弗雷曲线不是模曲线谷山-志村猜想怀尔斯证明半稳定椭圆曲线都是模曲线从而费马方程无解九、超越数论——代数与分析的相遇9.1 代数数与超越数定义代数数满足整系数多项式方程的复数超越数不是代数数的复数例子代数数2 , 1 5 2 \sqrt{2}, \frac{1\sqrt{5}}{2}2​,215​​黄金比例, 所有有理数超越数π , 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​在代数数域上线性无关。推论e ee是超越数取α 1 1 \alpha_11α1​1π \piπ是超越数若π \piπ是代数数则i π i\piiπ也是由定理e i π − 1 e^{i\pi} -1eiπ−1与代数数线性无关矛盾9.3 希尔伯特第七问题问题a b a^bab的超越性a aa代数且不为0,1b 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年选择大素数p , q p,qp,q计算N p q NpqNpqφ ( N ) ( p − 1 ) ( q − 1 ) \varphi(N)(p-1)(q-1)φ(N)(p−1)(q−1)选择e ee使gcd ⁡ ( e , φ ( N ) ) 1 \gcd(e,\varphi(N))1gcd(e,φ(N))1计算d dd使e d ≡ 1 ( m o d φ ( N ) ) ed \equiv 1 \pmod{\varphi(N)}ed≡1(modφ(N))公钥( N , e ) (N,e)(N,e)私钥( N , d ) (N,d)(N,d)加密c ≡ m e ( m o d N ) c \equiv m^e \pmod{N}c≡me(modN)解密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_{n1} \equiv ax_n b \pmod{m}xn1​≡axn​b(modm)算法分析模运算的复杂度分析结语数论之美数论始于最简单的计数对象——整数却发展出了数学中最深刻、最优雅的理论。从欧几里得对素数无穷的巧妙证明到高斯二次互反律的对称之美从费马大定理的千年谜题到黎曼猜想的深邃奥秘数论不断展示着简单问题的深刻性儿童都能理解的质数蕴含着宇宙的密码纯粹与应用的统一最抽象的定理如中国剩余定理、欧拉定理成为现代通信的基石人类智慧的传承从古希腊到现代无数天才为之添砖加瓦数论如一面镜子既映照出整数世界的完美秩序也反映出人类理性探索的无限可能。在这个数字时代这门最古老的数学分支正焕发着新的生机继续引领我们探索数学——以及宇宙——的根本奥秘。“数学是科学的皇后数论是数学的皇后。” ——高斯