Mas's Blog
Masellum 的生活日志
数论学习笔记

基本定义

对于两个自然数 a,ba, b,如果 a=kba = kbb0b \neq 0,那么我们说 bb 整除 aa 或者说 aabb 整除,记作 bab \mid a;否则 bb 不整除 aa,记作 bab \nmid a。如果 bab \mid a,那么我们说 bbaa 的因数,aabb 的倍数。如果一个数同时是两个数的因数,那么这个数是这两个数的公因数。如果两个数除了 11 之外没有别的公因数,那么这两个数互质,记作 a  ba \ \bot \ b

欧几里得算法

欧几里得算法又称辗转相除法,用来求两个数的最大公因数。依据是 gcd(a,b)=gcd(b,a % b)\gcd(a, b) = \gcd(b, a\ \% \ b)

证明:

gcd(a,b)=gcd(b,a % b)    gcd(a,b)=gcd(b,ab)\gcd(a, b) = \gcd(b, a\ \% \ b) \iff \gcd(a, b) = \gcd(b, a - b)。使用反证法证明。设 r=gcd(a,b)r = \gcd(a, b),则 rr 也是 b,abb, a - b 的因数。如果 rgcd(b,ab)r \neq \gcd(b, a - b),那么一定有一个数 ss 满足 s=gcd(b,ab)s = \gcd(b, a - b)。此时 sbs \mid bsabs \mid a - b,故 sas \mid a,故 ss 也是 a,ba, b 的公因数。但 s>r=gcd(a,b)s \gt r = \gcd(a, b),产生矛盾,故不可能有符合条件的 ss,故 r=gcd(b,ab)r = \gcd(b, a - b)

证毕。

代码:

时间复杂度为对数级别。

关于最大公约数还有一个性质是 gcd(a,b)×lcm(a,b)=a×b\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b

证明:

根据算术基本定理,a,ba, b 均可表示成如下形式:

a=p1a1p2a2pnanb=p1b1p2b2pmbm \begin{aligned} a = p_1^{a_1}p_2^{a_2} \ldots p_n^{a_n}\\ b = p_1^{b_1}p_2^{b_2} \ldots p_m^{b_m}\\ \end{aligned} 其中 pip_i 为质数。我们将 aabb “对齐”,也就是将他们的质因数逐个对应,只在一个数里出现过的令其指数为 00。显然 gcd(a,b)=i=1max(n,m)pimin(ai,bi)lcm(a,b)=i=1max(n,m)pimax(ai,bi) \begin{aligned} \gcd(a, b) = \prod_{i = 1}^{\max(n, m)}p_i^{\min(a_i, b_i)}\\ \operatorname{lcm}(a, b) = \prod_{i = 1}^{\max(n, m)}p_i^{\max(a_i, b_i)} \end{aligned} 故显然 gcd(a,b)×lcm(a,b)=a×b\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b

扩展欧几里得算法

扩展欧几里得算法用来求解形如 ax+by=gcd(a,b)ax + by = \gcd(a, b) 的不定方程。 ax+by=gcd(a,b)=gcd(b,a % b) \begin{aligned} ax + by &= \gcd(a, b) \\[2ex] &= \gcd(b, a \ \% \ b) \\[2ex] \end{aligned} 因此我们可以列出新的方程 bx+(a % b)y=gcd(b,a % b)=bx+(aab×b)y=ay+b(xab×y) \begin{aligned} bx' + (a \ \% \ b)y' &= \gcd(b, a \ \% \ b) \\[2ex] &= bx' + (a - \lfloor \frac{a}{b} \rfloor \times b) y' \\[2ex] &= ay' + b \cdot (x' - \lfloor \frac{a}{b} \rfloor \times y') \end{aligned}

x=y,y=xab×yx = y', y = x' - \lfloor \frac{a}{b} \rfloor \times y'。所以我们可以在进行欧几里得算法的同时递归得出每一组 a,ba, b 所对应的 x,yx, y 。递归终止条件是当 b=0b = 0x=1,y=0x = 1, y = 0。其实 $y $应该是可以随便取的,不过大家都取 $0 $(可能是为了方便计算)。这样便可得到不定方程的一组解。已经求出一组 x,yx, y 以后,ax+by=a(xb)+b(y+a)ax + by = a(x - b) + b(y + a),所以我们可以由一组解计算出其他解。

代码:

扩展欧几里得算法还可以用来计算 ax1(modb)ax \equiv 1 \pmod b 的同余方程。因为这种方程可以化为 ax+by=1ax + by = 1,当 gcd(a,b)=1\gcd(a, b) = 1a,ba, b 互质的时候此方程有解,其他情况无解。

质数

质数的定义不再重复。

算术基本定理

任意一个正整数都可以表示成如下形式: n=p1a1p2a2pnan n = p_1^{a_1}p_2^{a_2} \ldots p_n^{a_n} ,其中 pp 是质数。

质因数分解

分解 nn 的质因数的方法是,枚举所有小于等于 n\sqrt{n} 的数,如果这个数是 nn 的因数,那么就把这个数从 nn 中除去并记录它的指数增加了一;如果除完后这个数仍能整除 nn,那么继续除到无法整除为止。枚举完这些数以后如果 nn 被除后剩余的商仍不等于一,那么这个剩余的数就是 nn 的唯一一个大于 n\sqrt{n} 的质因数。这个算法的正确性十分显然,不再证明。

根据乘法原理,如果 n=p1a1p2a2pnann = p_1^{a_1}p_2^{a_2} \ldots p_n^{a_n},那么 nn 的因数个数为 i=1n(ai+1)\prod_{i=1}^n (a_i+1)

质数筛法

这里只记录线性筛相关知识,暴力筛和埃氏筛不再记录。

线性筛的基本思想是,每个合数只会被它的最小质因数筛去。

代码:

线性筛还可以用来预处理出一系列数论函数的值。

逆元

因为除法在取模意义下不封闭,因此如果我们想在取模意义下做“除法”,就要用到逆元。

如果 aa11(modp)a \cdot a^{-1} \equiv 1 \pmod p,那么我们就将 a1a^{-1} 记作 aa 在 模 pp 意义下的逆元。

求逆元的方法有若干种。

费马小定理

如果 pp 是质数,那么 ap11(modp)a^{p - 1} \equiv 1 \pmod p。所以 aap21(modp)a \cdot a^{p-2} \equiv 1 \pmod p,即 aa 在模 pp 意义下的逆元是 ap2a^{p - 2}。可以用快速幂在 O(logn)O(\log n) 的时间复杂度内求出 aa 的逆元。

线性求逆元

考虑取模的定义式: pmoda=ppa×a p \bmod a = p - \lfloor \frac{p}{a} \rfloor \times a 将这个式子放在模 pp 同余系下: pmodapa×a(modp) p \bmod a \equiv -\lfloor \frac{p}{a} \rfloor \times a \pmod p 两边同时乘以 (pmoda)1a1(p \bmod a)^{-1} \cdot a^{-1}a1pa×(pmoda)1(modp) a^{-1} \equiv -\lfloor \frac{p}{a} \rfloor \times (p \bmod a)^{-1} \pmod p 因为 (pmoda)1<a(p \bmod a)^{-1} \lt a,因此逆元可以线性递推得出。初始条件为 11=11^{-1} = 1。写代码的时候需注意负数取模。

代码:

积性函数与线性筛

积性函数

ff 是一个定义域为 N+\mathrm{N}^+ 的函数,如果对于任意两个互质的正整数 a,ba, b 都满足 f(ab)=f(a)f(b)f(a \cdot b) = f(a) \cdot f(b),那么称 ff 为积性函数。如果对于任意两个正整数(不要求互质)都满足 f(ab)=f(a)f(b)f(a \cdot b) = f(a) \cdot f(b),那么称 ff 为完全积性函数。

积性函数的性质

  1. 对于任意积性函数 ff 都有 f(1)=1f(1) = 1。证明略。

  2. 对于一个大于 11 的正整数 nn,设$ n = p_i^{a_i}$,其中 pip_i 为互不相同的素数,那么对于积性函数 fff(n)=f(piai)=f(piai) f(n) = f(\prod p_i^{a_i}) = \prod f(p_i^{a_i}) 对于完全积性函数 ff 还有 f(n)=f(pi)ai f(n) = \prod f(p_i)^{a_i} 证明略。

常见的积性函数

欧拉函数

定义欧拉函数 φ(n)\varphi(n) 为小于 nn 的正整数中与 nn 互质的数的个数。

根据容斥原理可以推出:

n=i=1mpiai n = \prod_{i = 1}^{m} p_i^{a_i} 其中 pip_i 为质数,那么 φ(n)=ni=1m(11pi) \varphi(n) = n \prod_{i = 1}^{m} (1 - \frac{1}{p_i}) (但是这个式子我暂时还不会证明(逃

欧拉函数的性质
  1. 欧拉函数是积性函数,但是不是完全积性函数。

    证明:设 a,ba, b 为两个互质的正整数,则 φ(a)=a(11pai)φ(b)=b(11pbi)φ(a)φ(b)=apaibpbi=ab(11pai)(11pbi) \begin{aligned} \varphi(a) &= a \prod (1 - \frac{1}{p_{a_i}}) \\ \varphi(b) &= b \prod (1 - \frac{1}{p_{b_i}}) \\ \varphi(a) \varphi(b) &= a \prod p_{a_i} \cdot b \prod p_{b_i} \\ &= ab \prod (1 - \frac{1}{p_{a_i}})(1 - \frac{1}{p_{b_i}}) \end{aligned} 因为 a,ba, b 互质,所以 pa1,pb2p_{a_1}, p_{b_2} 互不相同,所以 φ(a)φ(b)=φ(ab)\varphi(a)\varphi(b) = \varphi(ab)。显然若 a,ba, b 不互质则 φ(a)φ(b)=φ(ab)\varphi(a)\varphi(b) = \varphi(ab),因此欧拉函数不是完全积性函数。

  2. pp 为质数, kk 为正整数,那么 φ(pk)=pkpk1\varphi(p^k) = p^k - p^{k - 1}

    证明:我们考虑枚举小于 pkp^k 的正整数中与 pkp^k 不互质的数。显然这样的数都是 pp 的倍数。它们是: 1×p,2×p,,(pk11)×p 1 \times p, 2 \times p, \cdots, (p^{k-1} - 1) \times p 所以 φ(pk)\varphi (p^k) 的值为小于 pkp^k 的正整数的个数减去这些数中与 pkp^k 互质的数的个数。即 (pk1)(pk11)=pkpk1 (p^k - 1) - (p ^{k - 1} - 1) = p^k - p^{k - 1} 也可以从定义式直接证明。

  3. 欧拉定理:设 a,na, n 为两个互质的正整数,那么 aφ(n)1(modn)a^{\varphi(n)} \equiv 1 \pmod n

    证明:设 x1,x2,,xφ(n)x_1, x_2, \cdots, x_{\varphi(n)} 是小于 nn 的数中与 nn 互质的数,显然这些数有 φ(n)\varphi(n) 个。令 mi=axim_i = a \cdot x_i

    引理 1 :mimodnm_i \bmod n 的值互不相同。证明:设 ms>mrm_s \gt m_r。若 msmr(modn)m_s \equiv m_r \pmod n,则有 msmr=a(xsxr)=knm_s - m_r = a(x_s - x_r) = kn,即 na(xsxr)n \mid a(x_s - x_r)。但 a  na \ \bot \ n,而 xsxrnx_s - x_r \le n,故 na(xsxr)n \nmid a(x_s - x_r),故不可能有两个 mim_inn 同余。所以 φ(n)\varphi(n) 个数有 φ(n)\varphi(n) 个不同的余数。

    引理 2:(mimodn)  n(m_i \bmod n) \ \bot \ n。证明:设 rrmimodnm_i \bmod nnn 的公因数,则 axi=mi=pn+qrax_i = m_i = pn + qraxiax_inn 不互质。但 a  na \ \bot \ nxi  nx_i \ \bot \ n,所以 axi  nax_i \ \bot \ n,故 mimodnm_i \bmod nnn 不可能有大于 11 的公因数。

    由此可得 mim_inn 的余数是小于 nn 的数中与 nn 互质的数,即 {mimodn}={xi}\{m_i \bmod n\} = \{x_i\}

    mixi(modn)    aφ(n)xixi(modn)    (aφ(n)1)xi0(modn) \begin{aligned} &\hspace{6ex}\prod m_i \equiv \prod x_i &\pmod n \\ &\implies a^{\varphi(n)} \prod x_i \equiv \prod x_i &\pmod n \\ &\implies (a^{\varphi(n)} - 1) \prod x_i \equiv 0 &\pmod n \\ \end{aligned} 因为 xix_inn 互质,所以 aφ(n)10(modn)    aφ(n)1(modn) a^{\varphi(n)} - 1 \equiv 0 \pmod n \implies a^{\varphi(n)} \equiv 1 \pmod n 证毕。

    费马小定理是当 nn 是质数的时候的欧拉定理的一种特殊情况。

  4. 对于正整数 nndnφ(d)=n\sum_{d \mid n} \varphi(d) = n

    证明:当 n=1n = 1 时,原式显然成立。

    n=pkn = p^k,其中 pp 是质数时, dnφ(d)=i=0kφ(pi)=1+i=1kφ(pi)=1+i=1k(pi1+pi)=pi \begin{aligned} \sum_{d \mid n} \varphi(d) &= \sum_{i = 0}^{k} \varphi(p^i) \\ &= 1 + \sum_{i = 1}^k \varphi(p^i) \\ &= 1 + \sum_{i = 1}^k (-p^{i - 1} + p^i) \\ &= p^i \end{aligned} n=p1a1p2a2...pkakn = p_1^{a_1}p_2^{a_2}...p_k^{a_k} 时,利用积性函数的性质可以证明。

    证毕。

莫比乌斯函数

// 待续

其他常见积性函数

// 待续

线性筛

利用积性函数的性质,我们可以在线性筛质数的同时筛出积性函数的值。通用过程是考虑将所有数分为三类:

  1. 质数
  2. 最小质因子的指数是 11
  3. 最小质因子的指数大于 11

据说还有不需要分三种情况而直接按照最小质因子的指数计算的方法,但是我没学过也还不会这里就不讲(逃

欧拉函数

计算 φ(n)\varphi(n) 的值,按照上面的三类考虑:

  1. nn 是质数时,φ(n)=n1\varphi(n) = n - 1
  2. nn 的最小质因子 qq 的指数是 11 时,φ(n)=φ(mq)=φ(m)φ(q)\varphi(n) = \varphi(m \cdot q) = \varphi(m) \cdot \varphi(q)
  3. nn 的最小质因子 qq 的指数大于 11 时,φ(n)=φ(mq)=qφ(m)\varphi(n) = \varphi(m \cdot q) = q \cdot \varphi(m)。证明:φ(mq)=mq(11pi)=qm(11pi)=qφ(m)\varphi(m \cdot q) = m \cdot q \prod (1- \frac{1}{p_i}) = q \cdot m \cdot \prod (1- \frac{1}{p_i}) = q \cdot \varphi(m)

代码:

// 待补充:莫比乌斯反演

Finita la comedia.