初等数论2
0. 前言
$\qquad$此篇文章算是对数学那一章第二节课的内容做一个总结,因为那天y总经受不住山东人的热情(doge),小酌了一下,所以有些地方可能讲的稍微不严谨,后面有些许混乱, 我在这里整理说明了一些视频中容易使人疑惑的地方,希望大家看了之后能够解决自己的困惑,如果有帮助的话就点个赞支持一下谢谢!
1. 整数的性质
定理1 (带余除法):对于 $a,b\in \mathbb{Z}$,且 $b\ne 0$,一定存在一对整数 $q,r$,使得 $a = qb + r$.
证明:略.
定理2 (这是一个简单且有用的整除的定理):在 $\mathbb{Z}$ 中,若 $b|a_i,i=1,2,\dots,s$,则对 $\forall u_1,u_2,\dots,u_s$,都有$b|(u_1a_1+u_2a_2+\dots+u_sa_s)$.
证明:略.
以上两个定理比较简单, 这里就掠过了.
定理3: $d$ 是 $a, b$ 的最大公因数的充分必要条件是: $d$ 是 $b, r$ 的最大公因数.
证明: 必要性:若 $d$ 是 $a,b$ 的最大公因数,则 $d$ 当然是 $a,b$ 的因数,又因为 $r = a - qb$,因此由定理1,$d$ 也是 $r$ 的因数. 对于 $b$ 和 $r$ 的任意一个因数 $c$,因为$a = qb + r$,同样由定理2,可以得到 $c$ 也是 $a,b$ 的因数,因为 $d$ 是 $a,b$ 的最大公因数,因此 $c|d$,必要性得到证明. 充分性可类似证明.
定理4 (裴蜀定理):任给 $a,b\in \mathbb{Z}$,都存在 $a$ 与 $b$ 的一个最大公因数 $d$,且存在 $u,v\in \mathbb{R}$,使得 $ua + vb = d$. 特别的,若 $a,b$ 互素,则 有 $ua + vb = 1$.
证明: 由定理3可以得到如下式子:
$\qquad\qquad\qquad\qquad\qquad\qquad a = q_1b+r_1$
$\qquad\qquad\qquad\qquad\qquad\qquad b = q_2r_1+r_2$
$\qquad\qquad\qquad\qquad\qquad\qquad r_1 = q_3r_2+r_3$
$\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad \vdots $
$\qquad\qquad\qquad\qquad\qquad\qquad r_{s-3} = q_{s-1}r_{s-2} + r_{s-1}$
$\qquad\qquad\qquad\qquad\qquad\qquad r_{s-2} = q_{s}r_{s-1}+r_{s}$
$\qquad\qquad\qquad\qquad\qquad\qquad r_{s-1}=q_{s+1}r_s$
然后再反推回去,可以得到
$\qquad\qquad\qquad\qquad\qquad\qquad r_s = r_{s-2}-q_sr_{s-1}$
$\qquad\qquad\qquad\qquad\qquad\qquad = r_{s-2}-q_s(r_{s-3}-q_{s-1}r_{s-2})$
$\qquad\qquad\qquad\qquad\qquad\qquad = -q_sr_{s-3}+(1+q_sq_{s-1})r_{s-2}$
$\qquad\qquad\qquad\qquad\qquad\qquad \qquad\qquad\qquad\vdots$
$\qquad\qquad\qquad\qquad\qquad\qquad = ua + vb$
因此,我们找到了一种求任意两个整数 $a,b$ 最大公因数的方法,叫做辗转相除法或欧几里得算法 ,是由南宋时期的数学家秦九韶发明的算法. 后面还会提到他给出的另一个定理,又叫做大衍求一术,被称为中国剩余定理.
说明:以下三个互素整数的性质很有用, 大家可以记住它们
互素整数性质1:在整数 $\mathbb{Z}$ 中,若$a|bc$,且$(a,b)=1$,则$a|c$.
证明:因为$(a,b)=1$,由裴蜀定理可以得到存在 $u$ 和 $v$,使得 $ua+vb=1$. 把该等式两边同时乘以 $c$,可以得到 $uac+vbc=c$. 因为 $a|a$ 且 $a|bc$,由以上定理1可得 $a|c$.
互素整数性质2:在整数 $\mathbb{Z}$ 中,若 $a|c$,$b|c$,$(a,b) = 1$,则 $ab|c$.
证明:因为 $a|c$,可以得到存在 $h$,使得 $c = ha$,即 $b|ha$,由性质1可得,$b|h$,即存在 $g$,使得 $h = bg$,即$c = abg$,最终可以得到 $ab|c$.
互素整数性质3:在整数 $\mathbb{Z}$ 中,若$(a,c)=1$,$(b,c) = 1$,则$(ab,c) = 1$
证明:因为$(a,c)=1$,$(b,c) = 1$,则存在 $u_1,v_1,u_2,v_2$ 使得
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad u_1a + v_1c = 1$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad u_2b + v_2c = 1$
把含$a,b$ 的项放到等式左边然后两式相乘可以得到
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad u_1u_2ab = (1-v_1c)(1-v_2c)$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad = 1-v_1c-v_2c+v_1v_2c^2$
移项以后可以得到
$\qquad\qquad\qquad\qquad\qquad\qquad(u_1u_2)ab + (v_1 + v_2 - v_1v_2c)c = 1$
因此可以得到证明 $ab$ 与 $c$ 互素.
定理5:设 $p$ 是大于1的整数,则下列命题等价:
(1) $p$ 是素数;
(2) 对任意整数 $a$,都有 $p|a$ 或 $(p,a) = 1$;
(3) 对于整数 $a, b$,从 $p|ab$ 可以推出 $p|a$ 或 $p|b$;
(4) $p$ 不能分解成两个比 $p$ 小的正整数的乘积;
2. 欧拉函数与欧拉定理
定义:把 $Z_m$ 中可逆元的个数记作 $\varphi(m)$,称 $\varphi(m)$ 为欧拉函数.
我们可以立即推出,$\varphi(m)$ 就是指所有小于 $m$ 且与 $m$ 互素的数的个数.
定理6(该定理证明较复杂, 记住就行):设 $m=m_1m_2$,且 $m_1$ 与 $m_2$ 是互素的大于1的整数,则
$$ \varphi(m)=\varphi(m_1)\varphi(m_2) $$
推论:设 $m = p_1^{r_1}p_2^{r_2},\dots,p_s^{r_s}$,其中 $p_1,p_2,\dots,p_s$是两两不等的素数,则
$$
\varphi(m)=\varphi(p_1^{r_1})\varphi(p_2^{r_2})\dots\varphi(p_s^{r_s})
$$
$$
=p_1^{r_1-1}(p_1-1)p_2^{r_2-1}(p_2-1)\dots p_s^{r_s-1}(p_s-1)
$$
$$
=m\frac{p_1-1}{p_1}.\frac{p_2-1}{p_2}\dots\frac{p_s-1}{p_s}
$$
定理7(欧拉定理):设 $m$ 是大于1的正整数,如果整数 $a$ 与 $m$ 互素,那么
$$ a^{\varphi(m)}\equiv1(\text{mod }m) $$
证明
设集合 $A = $ { $ x_1(\text{mod }m), x_2(\text{mod }m),\dots, x_{\varphi{(m)}}(\text{mod }m) $ } 是小于 $m$ 的所有与 $m$ 互素的不同的数的集合(这里取模是为了与后面形式上同一,不取模肯定也是小于 $m$ 的).
然后再令 $B = $ {$ ax_1(\text{mod }m), ax_2(\text{mod }m),\dots,ax_{\varphi{(m)}}(\text{mod }m) $ }
因为都取了模,所以 $B$ 中所有元素也是小于 $m$ 的. 又因为 $a$ 与 $m$ 互素,每一个 $x$ 都与 $m$ 互素,由互素的性质3可以得到$ax_1$, $ax_2$,…,$ax_m$ 都与 $m$ 互素, 即$(ax_i, m) = 1, i = 1, 2, \dots, m$, 由裴蜀定理我们可以得到 $$(\text{集合}B\text{中每一个元素}, m) = 1.$$ 并且取完模后 $B$ 中的元素已经都小于 $m$了. 我们还可以进一步说明,$B$ 中所有的元素两两不同,若 $B$ 中存在相同的元素,即假设存在 $$ax_i(\text{mod }m) = ax_j(\text{mod }m) \iff ax_i \equiv ax_j (\text{mod }m),$$ 那么因为 $a$ 与 $m$ 是互素的,所以 $a$ 可以直接约掉,那么就会有$i\ne j,$ 有 $$x_i(\text{mod }m) = x_j(\text{mod }m)\iff x_i \equiv x_j (\text{mod }m)$$ 这就与A集合中元素互不相同这一前提出现了矛盾. 所以 $B$ 中元素也互不相同且和 $m$ 互素,并且 $A$ 集合 与 $B$ 集合元素的个数是相等的. 我们已经定义$A$ 是所有小于 $m$ 且与 $m$ 互素的整数个数,那么$B$ 中的这些元素肯定也是 $A$ 中这些元素,这不过是顺序换了一下,专业术语叫做集合 $A$ 元素的一个置换.
那么把集合 $A$ 内所有元素相乘与 $B$ 内所有元素相乘是相等的,再结合《初等数论1》里最后一块内容可以得到以下式子
$$
x_1x_2\dots x_{\varphi({m})} \equiv ax_1ax_2\dots ax_{\varphi({m})}(\text{mod }m)
$$
$$
x_1x_2\dots x_{\varphi({m})} \equiv a^{\varphi(m)}x_1x_2\dots x_{\varphi({m})}(\text{mod }m)
$$
所以
$$
a^{\varphi(m)}\equiv 1(\text{mod }m)
$$
以上就证明了欧拉定理.
3. 组合数的一个小定理与费马小定理
组合数的一个小定理:若 $p$ 是素数,则 $p | C_p^k$.
证明:$C_p^k$ 的公式为
$$C_p^k=\frac{p(p-1)\dots(p-k+1)}{k!},1\le k < p,$$ 当 $1\le k < p$ 时,$p\nmid k$,从而 $(k,p) = 1$. 于是有 $(k!,p)=1$. 由于 $k! | p(p-1)\dots(p-k+1)$,因此$$k!|(p-1)\dots(p-k+1),1\le k<p$$从而存在正整数$s_k$,使得 $(p-1)\dots(p-k+1)=s_kk!$. 由此得出,$C_k^p=ps_k,1\le k<p$,即$$p|C_p^k,1\le k<p$$
定理7(费马小定理):设 $p$ 是素数,则对于任意整数 $a$,都有
$$ a^p\equiv a(\text{mod }p) $$
$\qquad$ 关于费马小定理本身, y总可能记忆错乱了一点点, 它本身的说法就如定理6所述, 而不是直接把 $a^{p-1}\equiv 1(\text{mod }p)$ 称为费马小定理. 在费马小定理的基础上 $a$ 和 $p$ 互素的话, 才可以进一步得到 $a^{p-1}\equiv 1(\text{mod }p)$. 如果我们只知道 $a$ 和 $p$ 互素的话, 可以得到欧拉定理 $a^{\varphi(p)}\equiv 1(\text{mod }p)$, 这一点y总说的没问题. 然后进一步的如果 $p$ 是素数, 就会有$a^{p-1}\equiv 1(\text{mod }p)$, 因为我们知道 $p$ 是素数时, $\varphi(p) = p - 1$ (这里的$\varphi(p)$ 指的是欧拉函数). 而这里紧接着视频中y总就把$a^{p-1}\equiv 1(\text{mod }p)$说成是费马小定理了, 这是有一点点小问题的. 此时条件已经非常强了, 不仅 $p$ 是素数, $a$ 和 $p$ 也要互素. 而费马小定理是只要 $p$ 是素数就行, $a$ 和 $p$ 不必互素, 结论也是$a^p\equiv a(\text{mod }p)$, 而不是$a^{p-1}\equiv 1(\text{mod }p)$, 当然$a^{p-1}\equiv 1(\text{mod }p)$可以由 $a$ 和 $p$ 互素直接推出来. 在快速幂求逆元那个题目中,y总直接把 $a$ 给约掉了,但是理论上是不能直接约的,$a$ 要与 $p$ 互素才能直接约,但这并不影响答案的正确性. 当$a$ 与 $p$ 互素时能直接约掉就不说了, 那么当不互素时, 因为$p$是素数, 所以就只会有一种情况, 即$a$是$p$的倍数, 此时有
$$
np\equiv np\times b\times x (\text{mod }p)
$$
我们要想求满足这个式子的$x$很容易可以看出, $x$是可以取任意值的, 因为无论$x$取什么, 式子左右两端都是同余0.
而费马小定理的证明可由欧拉定理直接得到,证明如下:
证明:费马小定理是欧拉定理的一个特例,可以由欧拉定理直接得到:若 $p$ 是素数且 $(a,p) = 1$,则可以直接得到$\varphi(p) = p - 1$,可以直接证得 式 ($a^{p - 1}\equiv 1(\text{mod } p)$) 式成立. 又因为模 $p$ 同余的反身性,可得到 $a\equiv a(\text{mod }p)$,因此由下面提到的小定理可以得到 $a^p\equiv a(\text{mod }p)$成立. 若 $(a,p) \ne 1$,则 $p|a$,于是 $p|a^p$. 从而$a^p\equiv a(\text{mod }p)$. 定理得证.
注:这里提一个小定理:当 $a\equiv b(\text{mod }m)$,$c\equiv d(\text{mod } m)$,有$a+c\equiv b+d(\text{mod }m)$,$ac\equiv bd(\text{mod }m)$.
题目1:快速幂求逆元
#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int qmi(ll a, ll k, ll p) {
int res = 1;
while (k) {
if (k & 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
int main() {
cin >> n;
while (n--) {
int a, p;
cin >> a >> p;
int res = qmi(a, p - 2, p);
if (a % p) printf("%d\n", res);
else printf("impossible\n"); // 若a是p的倍数,则无解,因为a,p互质才能由欧拉定理推出一定有逆元
}
return 0;
}
题目2:扩展欧几里得算法
$\qquad$ 本题需要注意的点可能就是x与y互换位置了, 我给出了不互换位置的写法. 而互换位置方便在哪里,大家可以琢磨一下(其实就是在函数每一层退出的时候,形参本身的变换让我们少用了一个中间变量t)
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
// 不在本层调换
int t = x;
x = y;
y = t - a / b * y;
// y -= a / b * x; // 在本层调换,把上面三行注释, 这一行取消注释, 把exgcd(b, a%b, x, y)中x, y调换位置也对.
return d;
}
int main() {
int n;
cin >> n;
while (n--) {
int a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
return 0;
}
4. 中国剩余定理
定理8:一般地,设 $m_1$,$m_2$,$\dots$, $m_s$ 是两两互素的大于 1 的整数,$b_1,b_2,\dots,b_s$是任意给定的整数,一次同余方程组
$$
x\equiv b_i(\text{mod }m_i), i= 1, 2, \dots, s
$$
在 $Z$ 中有解,它的全部解是
$$
c+km_1m_2\dots m_s,\qquad k\in Z
$$
其中
$$
c=b_1v_1\prod\limits_{j\ne 1}m_j+b_2v_2\prod\limits_{j\ne 2}m_j+\dots+b_sv_s\prod\limits_{j\ne s}m_j
$$
$v_i$ 满足 $u_im_i+v_i\prod\limits_{j\ne i}m_j=1,i=1,2,\dots,s$.
证明:由于 $m_1$,$m_2$,$\dots$,$m_s$ 两两互素,因此对于 $i\in\{1,2,\dots,s\}$ 有
$$
\left(m_i,\prod\limits_{j\ne i}m_j \right)=1,
$$
从而存在 $u_i,v_i\in Z$,使得
$u_i,v_i\in Z$,使得
$$
u_im_i+v_i\prod\limits_{j\ne i}m_j=1
$$
由上式得
$$
v_i\prod\limits_{j\ne i}m_j=1 - u_im_i
$$
从而有
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad v_i\prod\limits_{j\ne i}m_j\equiv 1(\text{mod }m_i)$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad v_i\prod\limits_{j\ne i}m_j\equiv 0(\text{mod }m_k),\quad k\ne i$
由于同余方程组得解应当满足模 $m_i$ 同余于 $b_i,(i=1,2,\dots,s)$,因此,令
$$
c=b_1v_1\prod\limits_{j\ne 1}m_j+b_2v_2\prod\limits_{j\ne 2}m_j+\dots+b_sv_s\prod\limits_{j\ne s}m_j
$$
则
$$
c\equiv b_i(\text{mod }m_i)
$$
其中$i = 1,2,\dots,s$,因此 $c$ 是同余方程组的一个解.
若 $d$ 也是同余方程组的一个解,则
$$
c\equiv d(\text{mod }m_i),i=1,2,\dots,s.
$$
从而
$$
m_i | (c-d)\qquad i=1,2,\dots,s.
$$
由于$m_1,m_2,\dots,m_s$ 两两互素,因此
$$
m_1m_2\dots m_s|(c-d)
$$
由此得出
$$
c\equiv d(\text{mod }m_1m_2\dots m_s)
$$
那么,它的全部解就是
$$
c+km_1m_2\dots m_s,\qquad k\in Z
$$
题目三:线性同余方程
$\qquad$ $ax-my = b$ 即 $ax+my’ = b$,用扩展欧几里得算法求出$x$的值以及最大公因数$d$,若$b$是$d$的倍数,把$x$变为$b/d$倍即可.
#include<bits/stdc++.h>
using namespace std;
int n;
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;
}
int main() {
cin >> n;
while (n--) {
int a, b, m;
cin >> a >> b >> m;
int x, y;
int d = exgcd(a, m, x, y);
if (b % d) puts("impossible");
else printf("%d\n", b / d * (long long)x % m);
}
return 0;
}
题目四:表达整数的奇怪方式
$\qquad$由题意得到, 对于前两个方程, 有$$x\equiv a_1 (\text{mod } m_1)$$ 和 $$x\equiv a_2 (\text{mod } m_2).$$
那么我们可以得到$$k_1m_1 + a_1 = k_2m_2 + a_2.$$ 即$$k_1m_1-k_2m_2 = a_2-a_1.$$由扩展得欧几里得算法, 我们可以得到 $k_1$ 和 $k_2$ 的值. 我们只需要用到$k_1$. 并且我们知道 $k_1$ 和 $k_2$ 的解不是唯一的, 对于取任意 $k$ 的 $k_1+k\frac{m_2}{d}$ 来替换 $k_1$, 取任意 $k$ 的 $k_2+k\frac{m_1}{d}$ 来替换 $k_2$. 效果都是一样的. 都满足上式. 所以我们得到一个关于这两个方程的通解$$x = (k_1 + k\frac{m_2}{d})m_1 + a_1$$ 代码里面含有 $\frac{m_2}{d}$ 的那句比较长的代码(for
循环倒数第三句)就是为了找到一个最小的正整数 $k’$, 使得$$x = k’m_1 + a_1,$$ 只不过仍然用 $k_1$来表示 $k’$(for
循环倒数第四句). 此时$$x = k_1m_1 + a_1$$就是方程的解. 此时我们只是算出来了前两个方程的解, 而我们可以对通解进一步的化简得到$$x = k_1m_1 + a_1 + k\frac{m_1m_2}{d}.$$ 这个方程意味着$$x\equiv k_1m_1+a_1 (\text{mod }\frac{m_1m_2}{d})$$ 我们把 $k_1m_1+a_1$ 整体再换成 $a_1$, 把$\frac{m_1m_2}{d}$整体换成 $m_1$ (for
循环最后两句), 此时就会重新得到 $$x\equiv a_1 (\text{mod } m_1),$$ 此时它看起来仍旧是一个式子, 但里面的 $x$ 已经是符合前两个方程的了. 我们继续读入后面的方程, 不断循环迭代合并, 不断求出满足前两个式子、前三个式子、…前 $n$ 个式子的解.
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
ll m1, a1, x = 0;
cin >> m1 >> a1;
for (int i = 0; i < n - 1; i++) {
ll m2, a2, k1, k2;
cin >> m2 >> a2;
ll d = exgcd(m1, m2, k1, k2);
if ((a2 - a1) % d) { // 无解
x = -1;
break;
}
k1 *= (a2 - a1) / d; // 得到k1.
k1 = ( k1 % (m2 / d) + (m2 / d) ) % (m2 / d);
a1 = k1 * m1 + a1; // 此时a1就是答案. 为了和只有一个方程的情况保持一致, 没有必要每次都给x赋值.
m1 = m1 / d * m2;
}
if (x != -1) x = (a1 % m1 + m1) % m1; // 处理只有一个方程的情况, 最后再给x赋值.
printf("%lld\n", x);
return 0;
}
5.结语
$\qquad$到这里,第二节课大部分的问题已经尽我所能做了说明, 关于高斯消元求方程组或求异或方程组,它是一个比较独立的部分,按照流程来解就行. 第三节课的内容主要是求组合数,也用到了相当多本文的知识,主要引入了卢卡斯定理和卡特兰数. 第四节博弈论的部分可能后面会出专题总结,主要是$SG$函数.
那么因为 a与 m是互素的,所以 a可以直接约掉,这是因为什么呀?
汗。。。这属于初中知识吗
感谢老哥,检查源代码也让我自己整理的时候省了很多手打公式的时间
欧拉定理证明的最后一步约去一堆x,我想的是用同余的定义来解释的。不知道大佬有没有什么更好的理解思路或者定理啥的来解释为什么能左右同时约去。
求pdf版本
感谢分享
# 已收藏