数论学习笔记（约数篇二）

本文介绍欧拉函数、同余以及拓展欧几里得算法。

欧拉函数

定义

1 到 $N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。

性质

显然，如果 $N$ 为质数，则 $\varphi(N)=N-1$

欧拉函数为 积性函数： 若 $\gcd(a,b)=1$，则 $\varphi(ab)=\varphi(a)\varphi(b)$。

若 $n=p^{k}$，$p$ 为质数，则 $\varphi(n)=n(1-\dfrac{1}{p})$。

证明：
若 $x$ 与 $p^{k}$ 不互质，则有 $p|x$ 成立。
$x$ 共有 $\dfrac{n}{p}$ 个，因此 $\varphi(n)=n-\dfrac{n}{p}=n(1-\dfrac{1}{p})$

若 $N=p\_{1}^{c\_{1}}p\_{2}^{c\_{2}}...p\_{m}^{c\_{m}}$，则：
$\varphi(N)=N \times \dfrac{p\_{1}-1}{p\_{1}} \times \dfrac{p\_{2}-1}{p\_{2}} \times ... \times \dfrac{p\_{m}-1}{p\_{m}}$
$\varphi(N)=N \times \left ( 1-\dfrac{1}{p\_{1}} \right ) \times \left ( 1-\dfrac{1}{p\_{2}} \right ) \times ... \times \left ( 1-\dfrac{1}{p\_{m}} \right )$
即：
${\small \varphi \left ( n \right ) = n \times \prod_{i=1}^{m} \left ( 1-\frac{1}{p_{i}} \right )} $

证明：$\varphi$ 是积性函数。把 $n$ 拆成 $p\_{i}^{a\_{i}}$ 的乘积形式可立即得证。

代码

我们只要在分解质因数时顺便将欧拉函数求出来就好了。

int phi(int n) 
{
	int ans = n;
	for (int i = 2; i <= sqrt(n); i++) 
	{
		if (n % i == 0) 
		{
			ans = ans / i * (i - 1);
			while (n % i == 0)n /= i;
		}
	}
	if (n > 1)ans = ans / n * (n - 1);
	return ans;
}

同余

定义

若 $a \bmod {m} = b \bmod {m}$ ，则称 $a$ 与 $b$ 同余，写作 $a \equiv b \pmod{m}$

同余类、剩余系

对于一个集合 $\{ x|x=a+km,a \in \left [ 0,m-1 \right ] , k \in Z \}$ 的所有数模 $m$ 同余，余数都是 $a$ 。该集合被称为一个模 $m$ 的同余类，简记为 ā。
模 $m$ 的同余类一共 $m$ 个，它们构成 $m$ 的完全剩余系。
1 到 $m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$ 个，它们构成 $m$ 的简化剩余系

欧拉定理

若正整数 $a$，$n$ 互质，则 $a^{\varphi(n)} \equiv 1\pmod{n}$，其中 $\varphi(n)$ 为欧拉函数。

证明

设 $S=\{ a\_{1},a\_{2},...,a\_{\varphi(n)} \}$ 为 $n$ 的简化剩余系。
设 $a$ 与 $n$ 互质。
$\because a \equiv 1\pmod{n}$，$aa\_{1} \equiv 1 \pmod{n}$
$\therefore aa\_{1} \equiv 1 \pmod{n}$
同理，$aa\_{2},aa\_{3},...,aa\_{\varphi(n)}\equiv 1 \pmod{n}$
$\therefore aa\_{1} \times aa\_{2} \times...\times aa\_{\varphi(n)}\equiv1\pmod{n}$
$\therefore a^{\varphi(n)}\left ( a\_{1}a\_{2}...a\_{\varphi(n)} \right )\equiv a\_{1}a\_{2}...a\_{\varphi(n)} \pmod{n}$
$\therefore a^{\varphi(n)}\equiv 1 \pmod{n}$

费马小定理

若 $p$ 为质数，则对于任意整数 $a$，有 $a^{p}\equiv a \pmod{p}$，即 $a^{p-1}\equiv 1\pmod{p}$
证明太简单了，懒得证（用欧拉函数和欧拉定理证）

扩展欧几里得算法

贝祖定理（裴蜀定理）

定义

对于任意整数 $a$，$b$，存在一对整数 $x$，$y$，满足 $\mathbf{ax + by = \gcd(a,b)}$。特别地，一定存在 $x$，$y$ 满足 $ax + by = d$。
等价的表述：不定方程 $ax + by = c$ （$a$，$b$，$c$ 为整数）有解的充要条件为 $\gcd(a,b)| c$
推论：$a$，$b$ 互质等价于 $ax + by = 1$ 有解

原理

考虑如何求得 $ax + by = d$ 的一个解。这里 $d = \gcd(a,b)$

考虑使用欧几里德算法的思想，令 $a = bq + r$，其中 $r= a \bmod b$；递归求出 $bx + ry = d$ 的一个解。

设求出 $bx + ry = d$ 的一个解为 $x = x\_{0}$，$y = y\_{0}$，考虑如何把它变形成 $ax + by = d$ 的解。

将 $a = bq + r$ 代入 $ax + by = d$、化简得 $b(xq + y)+ rx = d$

我们令 $xq + y = x\_{0}$，$x = y\_{0}$，则上式成立

故 $x=y\_{0}$，$y=x\_{0}-y\_{0}q$ 为 $ax + by = d$ 的解

边界情况：$b = 0$ 时，令 $x = 1$，$y = 0$

代码

int exgcd(int a, int b, int &x, int &y) 
{
	if (!b) 
	{
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

求出 ax + by = c 的所有解

先用 exgcd 求出任意一个解 $x\_{0}$ 和 $y\_{0}$。
则 $ax\_{0}+by\_{0}=c$
再求出 $ax + by = 0$ 的最小（绝对值）解 $x' = \dfrac{b}{\gcd(a,b)}$ 和 $y' = \dfrac{-a}{\gcd(a,b)}$
则 $(ax\_{0}+by\_{0})+k(ax'+by')=c$
即 $a(x\_{0}+kx')+b(y\_{0}+ky')=c$
所有解就是 $x=x\_{0}+kx'$，$y=y\_{0}+ky'$，$k \in Z$

乘法逆元

若整数 b，m 互质，并且 $\mathbf{b|a}$，则存在一个整数 $x$，使得 $\mathbf{\dfrac{a}{b}\equiv a \times x\pmod{m}}$。
称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1} \pmod{m}$。
可以推得：当 $m$ 为质数时，$b^{m-2}$ 即为 $b$ 的乘法逆元（即 $x$ ）。
那么咋求逆元捏？

快速幂求逆元

快速幂

快速幂是啥？
可以看成是二进制优化的用来求 $\mathbf{a^{b}\bmod p}$ 的东西。

代码

求逆元相当于求 $b^{p-2}\bmod p$，所以能用快速幂求。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int unsigned long long
using namespace std;
const int N = 3000101;
int n, m;
inline int qm(int a, int k, int p) 
{
	int ans = 1;
	while (k) 
	{
		if (k & 1)ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) printf("%lld\n", qm(i, m - 2, m));
	return 0;
}

扩展欧几里得算法（贝祖定理）求逆元

求逆元又等价于求 $ax + by = 1$
所以可以直接上板子。

代码

int inv(int a, int b) 
{
	int x, y;
	exgcd(a, b, x, y);
	return x;
}

线性求逆元

在求 $i$ 的逆元时，

$\because p=\left \lfloor \dfrac{p}{i} \right \rfloor \times i+p \bmod i$（⌊ ⌋为向下取整），

令 $a = \left \lfloor \dfrac{p}{i} \right \rfloor$，$b = p \bmod i$，

$\therefore p=a \times i+b$

$\because a \times i+b=p$

$\therefore a\times i+b=0 \pmod{p}$

$\therefore a\times i=-b \pmod{p}$

$\therefore i=-\dfrac{b}{a} \pmod{p}$

$\therefore i^{-1}=- \dfrac{a}{b}\pmod{p}$

综上，$i$ 的逆元为 $\dfrac{-\left \lfloor \dfrac{p}{i} \right \rfloor\times i}{p \bmod i}$

设 $inv[ i ]$ 为 $i$ 的逆元，

$\because i^{-1}=-\dfrac{a}{b}\pmod{p}$

$\therefore inv[i]=-a\times b^{-1}\pmod{p}$

$\because b^{-1}=inv[b]$

$\therefore inv[i]=-\dfrac{a}{inv[b]}\pmod{p}$

$\therefore inv[i]=-\dfrac{\left \lfloor \dfrac{p}{i} \right \rfloor}{inv[p\bmod i]}\pmod{p}$

$\therefore inv[i]=\dfrac{p-\left \lfloor \dfrac{p}{i} \right \rfloor}{inv[p\bmod i]\bmod p}(\because x\bmod p=(x+p)\mod p)$

有了公式后就能用线性的复杂度求出每个数的逆元了。

代码

for (inv[1] = 1, i = 2; i <= n; ++i)
	inv[i] = (p - p / i) * inv[p % i] % p;

线性同余方程

形如 $ax ≡ c\pmod{m}$ 的方程（关于 $x$），称为线性同余方程。
该方程等价于 $ax + my = c$，有解条件为 $\gcd(a,m)| c$ 。
所以可以用 拓展$\gcd$ 来求。
求出 $x\_{0}$ 和 $y\_{0}$，满足 $ax\_{0}+my\_{0}=\gcd(a,m)$。
然后 $x=x\_{0}\times\dfrac{b}{\gcd(a,m)}$
$x$ 即为解。

剩下的下次再说吧。