# Summary # Cues # Notes 初等数论是数论的入门部分，主要研究整数的基本性质。这三个核心内容是： ## 1. 整除性 研究一个整数能否被另一个整数整除的性质： - **最大公约数(GCD)** 和 **最小公倍数(LCM)** - **辗转相除法**（欧几里得算法） - **算术基本定理**：每个大于1的整数都能唯一分解为素数的乘积 - **整除的性质**：如 a|b 且 a|c，则 a|(b+c) ## 2. 同余 研究整数除以某个数的余数关系： - **模运算**：a ≡ b (mod n) 表示 a 和 b 除以 n 的余数相同 - **同余方程**：如一次同余方程 ax ≡ b (mod n) - **中国剩余定理**：解同余方程组 - **费马小定理**：若 p 是素数，a 不被 p 整除，则 a^(p-1) ≡ 1 (mod p) - **欧拉定理**：费马小定理的推广 ## 3. 素数 研究只能被1和自身整除的数： - **素数判定**：如何判断一个数是否为素数 - **素数分布**：素数定理（素数的密度） - **特殊素数**：梅森素数、孪生素数 - **素数生成**：埃拉托斯特尼筛法 - **素性测试**：Miller-Rabin等概率算法 ## 经典问题示例 - 证明√2是[[无理数]]（用整除性） - 解方程 3x ≡ 7 (mod 11) - 证明有无穷多个素数（欧几里得证明） - [[哥德巴赫猜想]]（虽未解决，但属于初等数论范畴） 这些内容虽然"初等"，但却是整个数论大厦的基石，也是RSA加密等现代应用的数学基础。