【学习笔记】同余

发现当年学数论,4-6那本书第二三章基本上就是没学会,于是今天打算重学一遍。

发现还是很有意思的。并且发现读过的MO📚越多,这种东西就越好理解。

嗯,寓快于慢,藏巧于拙。

先定义一下解的「本质相同」:通常认为在模 $m$ 意义下的同余方程中 $x$ 和 $x+km(k\in\mathbb{Z_+})$ 是本质相同的。

同余的基本性质

1.

若 $ac\equiv bc\pmod m$,且 $(m,c)=d$,则 $a\equiv b \pmod{\frac{m}{d}}$ 。

因为 $(\frac{m}{d},\frac{c}{d})=1$ ,所以 $\frac{m}{d}|(a-b)$ 。

2、

若给定 $m_i(i=1,2,3\cdots)$ ,且 $\forall i$ 有 $a\equiv b\pmod {m_i}$,则有

由 $\forall i,m_i|(a-b)$ 可知 $(a-b)$ 是 $m_1,m_2,m_3\cdots$ 的一个公倍数。所以 ${[m_1,m_2,m_3\cdots ]} |(a-b)$ 。

练习题

1、证明

$11$ 整除 $a$ 的充分必要条件是 $a$ 写成十进制表示后,从低位到高位,奇数位数字和减去偶数位数字和内被 $11$ 整除。

我也不知道有啥好方法,编了一会儿觉得似乎 $100$ 进制的证法比较简单。就是考虑写成百进制的话会是这样:

发现 $100 \bmod 11$ 是 $1$ ,就很快乐:

然后考虑百进制转10进制,发现有

那么考虑 $10$ 在 $\pmod {11}$ 时等价于 $-1$ ,于是就可以知道

于是得证。

2、证明

$7/11/13$ 整除 $a$ 的充分必要条件是,最后三位数字与删去最后三位以后组成的数,所作之差被 $7/11/13$ 整除。

证明方法差不多?设后三位组成的数是 $b$ ,删去最后三位以后组成的数是 $c$ ,那么有

那么一定有

考虑 $1001=7\times 11\times 13$ ,所以可以知道 $1000 \bmod k\equiv -1 \pmod k$ 。于是得证。

剩余类相关理论

草,我是真觉得抽代入完门再来学这个比较合适。

于是因为内容太多了我就另开了一篇,想不到了吧?机智如我

一次同余方程

形如

的方程。

定理1

若 $(a,m)=1$ ,则该式只有 $1$ 解。

这是不难理解的。因为可以知道 $(1,2,3,\cdots m)$ 构成了模 $m$ 的一个完全剩余系,同时 $(a,2\cdot a,3\cdot a\cdots m\cdot a)$ 同样构成了模 $m$ 的一个完全剩余系。那么显然恰好一个整数使得 $aq\equiv b\pmod m$ . 所以解唯一。

定理2

(2.1) 若记 $(a,m)=d$ ,且 $d|b$ ,那么(1)式存在解。

(2.2) 在(2.1)的假设下,若(1)式存在解,那么解的个数为 $d$ 个。

首先不难知道(1)等价于 $ax+my=b$ 这个不定方程。那么(2.1)是显然的。

对于(2.2),考虑将(1)转化成

可知(1)和(2)的解是相同的。由定理1,且 $(\frac{a}{(a,m)},\frac{m}{(a,m)})=1$ 可知(2)的解是唯一的,设为 $t_0$

可知一定有 $0\leq t_0<\frac{m}{d}$ 。

因此(1)的全部解一定都是 $t_0+k\frac{m}{d} (k\in \mathbb{Z_+})$ 的形式。考虑 $k=0,1,2\cdots d-1$ 的时候,有

且由于其单调性可知这几个解互异。因此这 $d$ 个数在模 $m$ 下不同余。(证明了解至少有 $d$ 个)

另一方面,对(1)的任意一解 $t_0+k_0\frac{m}{d}$ ,令 $k_0=qd+r,0\leq r<d$ 代入得:

可知对于每个 $k_0$,均与某个 $0\leq k<d$ 时的解本质相同。(证明了解至多有 $d$ 个)。

因此,该式共有恰好 $d$ 个解。

一般解法技巧

有两种常用的技巧,都是基于将 $ax\equiv b\pmod m$ 转化为形式分式 $x\equiv \frac{b}{a}\pmod m$ 的基础上:

1、分子分母同乘一个与 $m$ 互质的数。

2、当 $(a,m)=1$ 时,分子可以加上 $m$ 的倍数。

注意到,限制「与 $m$ 互质」的目的是为了保证形式分式有意义,即只有 $(a,m)=1$,$a$ 在模 $m$ 意义下的逆元才有意义。

例题

一道毒瘤题

设 $p$ 为奇素数,$1<a<p$,则 $ax\equiv b\pmod p$ 的解为

考虑把 $(-1)^{a-1}$ 乘到上面的括号里去

然后就证完了。毒瘤就毒瘤在…我太不会…/dk

个人认为写成这样帅一点

中国剩余定理

若 $m_1,m_2\cdots m_k$ 为两两互素的正整数,记 $M=\prod m$ ,$r_i=\frac{M}{m_i}$ ,则一次同余方程

有唯一解 $x\equiv t$ ,且

其中 $q_i=\frac{1}{r_i}\pmod {m_i}$ 。

好难背啊

不过构造方式是很有趣的。大概就是考虑类似拉格朗日插值的构造方法,要找一堆 $\zeta_i$ 满足:

则可取

作为一组解。那么显然据此构造的方案满足这个条件。

另一方面,对于另一个解 $x_1$ 有

由于 $m_1,m_2\cdots m_k$ 两两互素,可知 $x_1\equiv x_0\pmod M$。即全部的解都可以表示成

exCRT

大概就是给出的 $m_i$ 不再互质的情况。

考虑此时普通的crt会出现什么问题。在 $m_i$ 彼此互质的情况下,可以知道 $r_i=\frac{M}{m_i}$ 保证 $(m_i,r_i)=1$,那也就保证了 $r_i$ 在模 $m_i$ 意义下存在逆元。但是当 $(m_i,r_i)>1$ 时,$q_i$ 就没有意义了。

考虑增量法。一开始有两个方程

那么有 $bt+a≡c \pmod d$ 用 exgcd 解出 $t≡t_0 \pmod{\frac{d}{(b,d)}}$

代回得 $x ≡ x_0 \pmod{[b, d]} $。这样迭代做下去就好了。感觉写这种代码还是要把变量分清,尽量写的清楚、松散一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std ;

const int N = 200010 ;

typedef long long ll ;

int n ;
ll A[N] ;
ll m[N] ;

ll exgcd(ll &x, ll &y, ll a, ll b){
if (!b){ x = 1, y = 0 ; return a ; }
ll g = exgcd(x, y, b, a % b), tmp = x ;
x = y ; y = tmp - a / b * y ; return g ;
}
ll exmul(ll a, ll b, ll mod){
ll res = 0 ;
while (b){
if (b & 1)
(res += a) %= mod ;
(a += a) %= mod ; b >>= 1 ;
}
return res ;
}
ll excrt(){
ll res, mod ;
ll a, b, c, d, M ;
ll x, y, t0, t, g, z ;
res = A[1] ; mod = m[1] ;
for (int i = 2 ; i <= n ; ++ i){
a = res, b = mod ;
c = A[i], d = m[i] ;
g = exgcd(x, y, b, d) ;
z = ((c - a) % d + d) % d ;
M = d / g ; if (z % g > 0) return -1 ;
t = exmul(x, (z / g), M) ; mod = mod * M ;
res = ((res + exmul(t, b, mod)) % mod + mod) % mod ;
}
return res ;
}
int main(){
ios :: sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ; cin >> n ;
for (int i = 1 ; i <= n ; ++ i) cin >> m[i] >> A[i] ;
ll op = excrt() ; if (op < 0) puts("hahaha") ; else cout << op ;
}

神奇的例题

CF338D

给出一个 $n × m$ 的数表, 其中第 $i$ 行第 $j$ 个数是 $\gcd(i, j)$,再给定一个长度为 $k$ 的数列 $\{a_n\}$, 判断其是否在数表的某一行出现过。

$n,m ≤ 10^{12},k ≤ 10^4$

一道有意思的题。考虑由于是要去寻找一行,所以行号是固定的。那么必须要有 $\mathrm{lcm}(a_1,a_2\cdots a_k)|x$ 。

考虑是否可以选用 $x=\mathrm{lcm}(a_1,a_2\cdots a_k)$ 做答案。注意到如果 $x=p\cdot \mathrm{lcm}(a_1,a_2\cdots a_k)$ 可行,那么一定有

那么发现,对于 $p$ 的任意一个因子,都满足该性质。所以取 $p=1$ 完全没有问题。

之后考虑去检验 $y$ 的合法性。令第一个元素之前的那个元素(跟答案没关系的)为 $(x,y)$ 。发现 $y$ 需要满足

注意到 $x$ 是所有 $a_i$ 的 $\rm lcm$ 。那么可以知道 $y+i$ 一定需要是 $a_i$ 的倍数,也就是

那么用 excrt 求出这个 $y$ 来即可。需要注意的是,这样并不代表 $y$ 合法,因为 $y+i$ 是 $a_i$ 的倍数等价于 $\gcd(y+i,x)=a_i\cdot q$ 。 所以为了验证是否合法,需要再从头判一遍。

注意到如果此时不存在答案,那么也一定不存在其他的答案。这一点是比较显然的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
namespace Sunzi{
ll A[N] ;
ll m[N] ;
ll exgcd(ll &x, ll &y, ll a, ll b){
if (!b){ x = 1, y = 0 ; return a ; }
ll g = exgcd(x, y, b, a % b), tmp = x ;
x = y ; y = tmp - a / b * y ; return g ;
}
ll exmul(ll a, ll b, ll mod){
ll res = 0 ;
while (b){
if (b & 1)
(res += a) %= mod ;
(a += a) %= mod ; b >>= 1 ;
}
return res ;
}
ll excrt(){
ll res, mod ;
ll a, b, c, d, M ;
ll x, y, t0, t, g, z ;
res = A[1] ; mod = m[1] ;
for (int i = 2 ; i <= k ; ++ i){
a = res, b = mod ;
c = A[i], d = m[i] ;
g = exgcd(x, y, b, d) ;
z = ((c - a) % d + d) % d ;
M = d / g ; if (z % g > 0) return -1 ;
t = exmul(x, (z / g), M) ; mod = mod * M ;
res = ((res + exmul(t, b, mod)) % mod + mod) % mod ;
}
return res ;
}
}
int main(){
using namespace Sunzi ;
cin >> n >> p >> k ; ll t = 1 ;
for (int i = 1 ; i <= k ; ++ i)
scanf("%lld", &base[i]), m[i] = base[i] ;
for (int i = 1 ; i <= k ; ++ i) A[i] = -i ; lcm = m[1] ;
for (int i = 2 ; i <= k ; ++ i){
t = m[i] * lcm, lcm = __gcd(lcm, m[i]), lcm = t / lcm ;
if (lcm > n) return puts("NO"), 0 ;
}
//cout << lcm << " " << t << endl ;
t = excrt() ; if (t < 0) return puts("NO"), 0 ;
for (ll i = t + 1 ; i <= t + k ; ++ i)
if (__gcd(i, lcm) != base[i - t]) return puts("NO"), 0 ;
if (t + k <= p) return puts("YES"), 0 ; else return puts("NO"), 0 ;
}