zhangxixi的博客

初等数论入门 · 全课基础练习卷 一、整除与素数（对应第1、2课） 用带余除法计算：−17-17−17 除以 555 的商和余数。 求 gcd⁡(126,84)\gcd(126, 84)gcd(126,84) 和 lcm(126,84)\text{lcm}(126, 84)lcm(126,84)。 使用扩展欧几里得算法，求整数 x,yx, yx,y 使得 48x+18y=gcd⁡(48,18)48x + 18y = \gcd(48, 18)48x+18y=gcd(48,18)。 将 180180180 分解为标准素因数乘积形式。 列举出 303030 以内的所有素数。 二、积性函数与...

初等数论入门 Lesson 10 连分数与佩尔方程 连分数 对于任意一个实数 α\alphaα，我们不断进行如下操作： αn=an+1αn+1\alpha_n=a_n+\dfrac 1 {\alpha_{n+1}} αn​=an​+αn+1​1​ 最终得到的序列：[a0;a1;a2;a3,⋯ ][a_0;a_1;a_2;a_3,\cdots][a0​;a1​;a2​;a3​,⋯] 记为简单连分数 且有理数一定数有限连分数，无理数一定是无限连分数 渐近分数 Convergents 我们对于无限连分数，截断到第 kkk 项，记为第 kkk 个渐近分数。 它们遵循二阶线性递推关系： {pk=a...

初等数论入门 Lesson 9 一次与二次不定方程 一次不定方程 解决：ax+by=cax+by=cax+by=c 其实就是我们之前学过的拓欧，步骤可以简化如下： 贝祖定理判定存在性 扩欧求特解 通解含参 不等式锁参 本原勾股数组 我们要找出满足 x2+y2=z2x^2+y^2=z^2x2+y2=z2 的正整数三元组 (x,y,z)(x,y,z)(x,y,z) 本原的概念（Primitive Pythagorean Triple）：gcd⁡(x,y,z)=1\gcd(x,y,z)=1gcd(x,y,z)=1 我们因此能推出几个性质： 性质一：不能同时为偶数 性质二：不能同时为...

初等数论入门 Lesson 8 二次剩余与二次互反律 二次剩余 Quadratic Residue ppp 为奇素数，且 p∤ap\not\mid ap∣a 给定 x2≡a(modp)x^2\equiv a \pmod p x2≡a(modp) 若 xxx 存在，则称 aaa 是模 ppp 的二次剩余（QR），否则是二次非剩余（QNR） 勒让德符号 Lengendre 符号 定义： (ap)={1,p∤a 且 a 是模 p 的二次剩余−1,p∤a 且 a 是模 p 的二次非剩余0,p∣a\left(\frac{a}{p}\right)= \begin{cases} 1, & ...

初等数论入门 Lesson 7 阶与原根 阶 Order 定义： 对于 gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1 ord⁡m(a)=min⁡{n∈Z∣an≡1(modm)}\operatorname{ord}_m(a)=\min\{n\in \mathbb Z\mid a^n\equiv 1\pmod m\} ordm​(a)=min{n∈Z∣an≡1(modm)} 即不断计算 a1,a2,…a^1,a^2,\dotsa1,a2,…，第一次出现余数为1，那个指数就是阶。 存在性证明： 由欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)}\equiv...

初等数论入门 Lesson 6 同余方程与中国剩余定理 剩余系 完全剩余系：一组数 a1,a2,…,ama_1,a_2,\dots,a_ma1​,a2​,…,am​ 称为模 mmm 的一个完全剩余系，如果它们分别取自模 mmm 的 mmm 个不同的剩余类。 有以下两种典型的剩余系： 最小非负剩余系：{0,1,2,…,m−1}\{0, 1, 2, \dots, m - 1\}{0,1,2,…,m−1} 绝对最小剩余系：{−⌊m2⌋,…,−1,0,1,…,⌈m2⌉}\left\{ -\left\lfloor \frac{m}{2} \right\rfloor, \dots, -1, 0...

初等数论入门 Lesson 5 欧拉函数 欧拉函数乘积公式 由第三课我们已知 φ(n)=n∏p∣n(1−1p)\boxed{\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)} φ(n)=np∣n∏​(1−p1​)​ 欧拉函数的积性我们也证明过： 构造剩余性 A={a∣1≤a≤m, gcd⁡(a,m)=1}A = \{a \mid 1 \le a \le m,\ \gcd(a,m) = 1\}A={a∣1≤a≤m, gcd(a,m)=1}，共 φ(m)\varphi(m)φ(m) 个； B={b∣1≤b≤n, ...

初等数论入门 Lesson 4 莫比乌斯反演 线性筛求 μ(1…n) μ(1)=1\mu(1)=1μ(1)=1 若 iii 是素数：μ(i)=−1\mu(i)=-1μ(i)=−1 若 imod  pj=0i\mod p_j=0imodpj​=0，即 pj2∣ip_j^2\mid ipj2​∣i，则 μ(i⋅pj)=0\mu(i\cdot p_j)=0μ(i⋅pj​)=0 否则：μ(i⋅pj)=−μ(i)\mu(i\cdot p_j)=-\mu(i)μ(i⋅pj​)=−μ(i) 基础函数与Dirichlet卷积 单位函数（卷积单位元） ε(n)={1,n=10,n>1\va...

初等数论入门 Lesson 3 积性函数与狄利克雷卷积 积性函数 Multiplicative Function 积性函数定义： f(1)=1,∀a,b  gcd⁡(a,b)=1⇒f(ab)=f(a)f(b)f(1)=1, \\ \forall a,b\;\gcd(a,b)=1 \Rightarrow f(ab)=f(a)f(b) f(1)=1,∀a,bgcd(a,b)=1⇒f(ab)=f(a)f(b) 完全积性函数（Completely Multiplicative Function）： f(1)=1f(ab)=f(a)f(b)f(1)=1\\ f(ab)=f(a)f(b)...

初等数论入门 Lesson 2 算术基本定理与素数分布初步 算术基本定理 Fundamental Theorem of Arithmetic n=p1a1p2a2…pkakn=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} n=p1a1​​p2a2​​…pkak​​ 欧几里得证明素数有无穷多个 我们使用欧几里得证明，使用反证法： 不妨设素数只有有限个，记为： p1,p2,…,pnp_1,p_2,\dots,p_n p1​,p2​,…,pn​ 令 N=p1p2…pn+1N=p_1p_2\dots p_n+1 N=p1​p2​…pn​+1 由算术基本定理，N>1N&...