4.4 求解同余方程
线性同余方程
a x ≡ b ( m o d m ) ， 其 中 ， m ∈ N + ， a , b ∈ N ， x 为 变 量 ， 这 样 的 方 程 称 为 线 性 同 余 方 程 ax \equiv b\ (mod\ m)，其中，m \in {N}^{+}，a,b \in N，x为变量，这样的方程称为线性同余方程 ax≡b (mod m)，其中，m∈N+，a,b∈N，x为变量，这样的方程称为线性同余方程
首先，这是个方程，所以x是变量，剩下的就是在确定a,b,m的值之后，确定x的可选值有哪些。解题思路是这样的：
g
c
d
(
a
,
m
)
=
1
，
且
a
,
m
∈
N
，
则
必
然
存
在
一
个
数
：
a
‾
,
称
为
a
模
m
的
逆
，
能
够
使
得
a
⋅
a
‾
≡
1
(
m
o
d
m
)
。
gcd(a,m)=1，且 a,m \in N，则必然存在一个数：\overline{a},称为a模m的逆，能够使得 a \cdot \overline{a} \equiv 1 (mod\ m)。
gcd(a,m)=1，且a,m∈N，则必然存在一个数：a,称为a模m的逆，能够使得a⋅a≡1(mod m)。
这里先举一个现实的例子：
假
设
a
=
3
,
m
=
7
，
则
−
2
⋅
3
≡
1
(
m
o
d
7
)
假设 a=3,m=7，则 -2 \cdot 3 \equiv 1 (mod\ 7)
假设a=3,m=7，则−2⋅3≡1(mod 7)
在上面的基础之上，再来看下面的推论，让我们先假定这个逆一定存在（接下来会证明这个值一定存在）。这个值如何帮助我们解决最开始的问题呢？
∵
a
x
≡
b
(
m
o
d
m
)
a
⋅
a
‾
⋅
x
≡
b
⋅
a
‾
(
m
o
d
m
)
a
⋅
a
‾
⋅
x
m
o
d
m
=
(
(
a
⋅
a
‾
m
o
d
m
)
×
(
x
m
o
d
m
)
)
m
o
d
m
a
⋅
a
‾
≡
1
(
m
o
d
m
)
x
m
o
d
m
=
b
⋅
a
‾
m
o
d
m
∴
x
≡
b
⋅
a
‾
(
m
o
d
m
)
\because ax \equiv b\ (mod\ m) \\ a \cdot \overline{a} \cdot x \equiv b \cdot \overline{a}\ (mod\ m) \\ a \cdot \overline{a} \cdot x\ mod\ m = ((a \cdot \overline{a}\ mod\ m) \times (x\ mod\ m))\ mod\ m \\ a \cdot \overline{a} \equiv 1\ (mod\ m) \\ x\ mod\ m = b \cdot \overline{a} \mod m \\ \therefore x \equiv b \cdot \overline{a}(\mod m)
∵ax≡b (mod m)a⋅a⋅x≡b⋅a (mod m)a⋅a⋅x mod m=((a⋅a mod m)×(x mod m)) mod ma⋅a≡1 (mod m)x mod m=b⋅amodm∴x≡b⋅a(modm)
这样就能获得了x的表达式。
那么问题就来了：
- a模m的逆一定存在吗？
- 如果存在，如何计算呢？
先是证明这个值一定存在。
∵
g
c
d
(
a
,
m
)
=
1
∴
∃
s
,
t
，
a
s
+
t
m
=
1
∴
(
a
s
+
t
m
)
≡
1
(
m
o
d
m
)
(
a
s
+
t
m
)
(
m
o
d
m
)
=
(
(
a
s
m
o
d
m
)
+
(
t
m
m
o
d
m
)
)
m
o
d
m
∵
t
m
m
o
d
m
=
0
∴
(
a
s
)
≡
1
(
m
o
d
m
)
，
这
里
s
就
是
作
为
a
的
逆
存
在
，
因
为
s
一
定
存
在
，
所
以
a
‾
一
定
存
在
\because gcd(a,m)=1\\ \therefore \exists s,t，as+tm=1 \\ \therefore (as+tm) \equiv 1 (mod\ m) \\ (as+tm)(mod\ m)=((as\ mod\ m)+(tm\ mod\ m))\ mod\ m \\ \because tm\ mod\ m=0 \\ \therefore (as)\equiv 1 (mod\ m)，这里s就是作为a的逆存在，因为s一定存在，所以 \overline{a} 一定存在
∵gcd(a,m)=1∴∃s,t，as+tm=1∴(as+tm)≡1(mod m)(as+tm)(mod m)=((as mod m)+(tm mod m)) mod m∵tm mod m=0∴(as)≡1(mod m)，这里s就是作为a的逆存在，因为s一定存在，所以a一定存在
接着就是这个值如何求，其实就是求贝祖系数
比如这里的
线
性
同
余
方
程
：
3
x
≡
4
(
m
o
d
7
)
的
解
是
什
么
？
线性同余方程：3x \equiv 4\ (\mod 7) 的解是什么？
线性同余方程：3x≡4 (mod7)的解是什么？
解题过程：
∵
5
⋅
3
−
2
⋅
7
=
1
∴
x
≡
5
⋅
4
(
m
o
d
7
)
≡
6
(
m
o
d
7
)
\because 5 \cdot 3 - 2 \cdot 7=1 \\ \therefore x \equiv 5 \cdot 4 (\mod 7) \equiv 6 (\mod 7)
∵5⋅3−2⋅7=1∴x≡5⋅4(mod7)≡6(mod7)
当然，答案不止一个，因为
−
8
≡
6
(
m
o
d
7
)
，
所
以
上
面
也
可
以
写
成
x
≡
−
8
(
m
o
d
7
)
-8 \equiv 6(\mod 7)，所以上面也可以写成 x \equiv -8 (\mod 7)
−8≡6(mod7)，所以上面也可以写成x≡−8(mod7)
中国剩余定理：多个同余方程组
上面介绍了一个线性方程组的解，但是如果有多个线性方程组的解需要整合时，该怎么处理呢？
比如：
x
≡
2
(
m
o
d
3
)
x
≡
3
(
m
o
d
5
)
x
≡
2
(
m
o
d
7
)
x \equiv 2(\mod 3)\\ x \equiv 3(\mod 5)\\ x \equiv 2(\mod 7)
x≡2(mod3)x≡3(mod5)x≡2(mod7)
问，这个时候如何求解？
暂时先不管上面的具体问题，我们把上面的方程组类比成下面的形式：
x
≡
a
1
(
m
o
d
m
1
)
x
≡
a
2
(
m
o
d
m
2
)
⋮
x
≡
a
n
(
m
o
d
m
n
)
且
g
c
d
(
m
i
,
m
j
)
=
1
x \equiv {a}_{1}(\mod {m}_{1}) \\ x \equiv {a}_{2}(\mod {m}_{2}) \\ \vdots \\ x \equiv {a}_{n}(\mod {m}_{n}) \\ 且 gcd({m}_{i},{m}_{j})=1
x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)且gcd(mi,mj)=1
解：
令
M
k
=
m
1
×
m
1
⋯
m
n
m
k
，
令
y
k
为
y
k
≡
M
k
(
m
o
d
m
k
)
，
即
y
k
为
M
k
模
m
k
的
逆
则
x
=
a
1
M
1
y
1
+
a
2
M
2
y
2
⋯
a
n
M
n
y
n
令 {M}_{k}=\frac{ {m}_{1} \times {m}_{1} \cdots {m}_{n} }{ {m}_{k} }，令{y}_{k}为\ {y}_{k} \equiv {M}_{k} (\mod {m}_{k})，即 {y}_{k}为 {M}_{k}模{m}_{k}的逆 \\ 则 x = {a}_{1}{M}_{1}{y}_{1}+{a}_{2}{M}_{2}{y}_{2} \cdots {a}_{n}{M}_{n}{y}_{n}
令Mk=mkm1×m1⋯mn，令yk为 yk≡Mk(modmk)，即yk为Mk模mk的逆则x=a1M1y1+a2M2y2⋯anMnyn
首先说明为什么上面的这种解法有效：
∵
（
a
1
M
1
y
1
+
a
2
M
2
y
2
⋯
a
n
M
n
y
n
）
m
o
d
m
j
=
(
(
a
1
M
1
y
1
m
o
d
m
j
)
+
(
a
2
M
2
y
2
m
o
d
m
j
)
⋯
(
a
n
M
n
y
n
m
o
d
m
j
)
)
(
m
o
d
m
j
)
当
n
≠
j
时
，
M
n
≡
0
(
m
o
d
m
j
)
，
因
为
M
n
中
有
m
j
，
所
以
上
面
可
以
化
简
为
a
j
M
j
y
j
m
o
d
m
j
同
时
，
(
(
a
j
m
o
d
m
j
)
(
M
j
y
j
m
o
d
m
j
)
)
(
m
o
d
m
j
)
可
以
化
简
为
a
j
m
o
d
m
j
∴
x
=
a
j
m
o
d
m
j
\because （{a}_{1}{M}_{1}{y}_{1}+{a}_{2}{M}_{2}{y}_{2} \cdots {a}_{n}{M}_{n}{y}_{n}）\ mod\ {m}_{j}= (({a}_{1}{M}_{1}{y}_{1} \mod {m}_{j})+({a}_{2}{M}_{2}{y}_{2} \mod {m}_{j}) \cdots ({a}_{n}{M}_{n}{y}_{n} \mod {m}_{j}))(mod\ {m}_{j}) \\ 当 n \neq j时，{M}_{n} \equiv 0 (\mod {m}_{j})，因为{M}_{n}中有{m}_{j}，所以上面可以化简为 \\ {a}_{j}{M}_{j}{y}_{j} \mod {m}_{j} \\ 同时，(({a}_{j} \mod {m}_{j})({M}_{j}{y}_{j} \mod {m}_{j}))(mod\ {m}_{j}) 可以化简为 \\ {a}_{j} \mod {m}_{j} \\ \therefore x={a}_{j} \mod {m}_{j}
∵（a1M1y1+a2M2y2⋯anMnyn） mod mj=((a1M1y1modmj)+(a2M2y2modmj)⋯(anMnynmodmj))(mod mj)当n=j时，Mn≡0(modmj)，因为Mn中有mj，所以上面可以化简为ajMjyjmodmj同时，((ajmodmj)(Mjyjmodmj))(mod mj)可以化简为ajmodmj∴x=ajmodmj
然后上面可以得到一个x的值，但是我们看上面，我们可以得出，其实x可以写成
令
M
=
l
c
m
(
m
1
,
m
2
,
m
3
⋯
m
n
)
，
d
=
x
m
o
d
M
，
则
x
=
d
(
m
o
d
M
)
令M=lcm({m}_{1},{m}_{2},{m}_{3} \cdots {m}_{n})，d=x mod M，则 \\ x=d\ (mod\ M)
令M=lcm(m1,m2,m3⋯mn)，d=xmodM，则x=d (mod M)
具体例子见书上248页的例5.
大整数的计算机算术
这一章简单来说就是如何通过减少值来加快计算速度，比如让你计算1+3的速度总是快过10000+30000。说具体的计算方法前，书上的原话
“
m
=
m
1
×
m
2
⋯
m
n
，
且
g
c
d
(
m
i
,
m
j
)
=
1
，
则
一
个
0
<
=
a
<
=
m
的
整
数
是
否
可
以
唯
一
表
示
成
(
a
m
o
d
m
1
,
a
m
o
d
m
2
,
a
m
o
d
m
3
,
⋯
a
m
o
d
m
n
)
m={m}_{1} \times {m}_{2} \cdots {m}_{n}，且 gcd({m}_{i},{m}_{j})=1，\\ 则一个0<=a<=m的整数是否可以唯一表示成 (a\mod {m}_{1},a\mod {m}_{2},a\mod {m}_{3}, \cdots a\mod {m}_{n})
m=m1×m2⋯mn，且gcd(mi,mj)=1，则一个0<=a<=m的整数是否可以唯一表示成(amodm1,amodm2,amodm3,⋯amodmn)
”
这样表示肯定没有问题的，因为在上面的中国剩余定理中我们证明了这样的数字是肯定存在的，至于在0~m之间是否唯一的问题了，在上面的最后我们也证明了这样的x的值是唯一的。
或者换个角度思考这个问题。
这样的数字差一点都不行：
例子：
将 123684和413456的加法转换成100内的加减
∵ 这 里 选 择 100 以 内 的 4 个 数 99 ， 98 ， 97 ， 95 123684 m o d 99 = 33 , 123684 m o d 98 = 8 , 123684 m o d 97 = 9 , 123684 m o d 95 = 89 ， 所 以 将 123684 改 写 成 ( 33 , 98 , 97 , 95 ) 同 理 413456 改 写 成 ( 32 , 92 , 42 , 16 ) \because 这里选择100以内的4个数 99，98，97，95 \\ 123684 \mod 99=33 ,123684 \mod 98=8,123684 \mod 97=9,123684 \mod 95=89，所以将 123684 改写成 (33,98,97,95) \\ 同理 413456 改写成 (32,92,42,16) ∵这里选择100以内的4个数99，98，97，95123684mod99=33,123684mod98=8,123684mod97=9,123684mod95=89，所以将123684改写成(33,98,97,95)同理413456改写成(32,92,42,16)
然后12368+413456可以归纳为
(
(
33
+
32
)
m
o
d
99
,
(
98
+
92
)
m
o
d
98
,
(
97
+
42
)
m
o
d
97
,
(
95
+
16
)
m
o
d
95
)
即
(
65
,
2
,
51
,
10
)
((33+32)\mod 99,(98+92)\mod 98,(97+42)\mod 97,(95+16)\mod 95) \\ 即\\ (65,2,51,10)
((33+32)mod99,(98+92)mod98,(97+42)mod97,(95+16)mod95)即(65,2,51,10)
上面计算的原理见这里的同余种的公式
然后如果要原始的值，需要计算
x
≡
65
(
m
o
d
99
)
x
≡
2
(
m
o
d
98
)
x
≡
51
(
m
o
d
97
)
x
≡
10
(
m
o
d
95
)
x \equiv 65 (mod\ 99) \\ x \equiv 2 (mod\ 98) \\ x \equiv 51 (mod\ 97) \\ x \equiv 10 (mod\ 95)
x≡65(mod 99)x≡2(mod 98)x≡51(mod 97)x≡10(mod 95)
这样的方式，可以加快计算速度，只有需要原来的值时，才需要进行100之外的计算。
费马小定理
“
如
果
p
为
素
数
，
且
a
∈
N
，
a
不
能
被
p
整
除
，
则
a
p
−
1
≡
1
(
m
o
d
p
)
，
并
且
a
p
≡
a
(
m
o
d
p
)
如果p为素数，且a \in N，a不能被p整除，则\\ {a}^{p-1} \equiv 1 (mod\ p)，并且 \\ a^p \equiv a (mod\ p)
如果p为素数，且a∈N，a不能被p整除，则ap−1≡1(mod p)，并且ap≡a(mod p)
”
证明：
二项式展示公式
a
p
=
(
1
+
(
a
−
1
)
)
p
=
∑
k
=
0
p
C
p
k
1
(
p
−
k
)
(
a
−
1
)
k
,
C
p
k
=
p
!
(
p
−
k
)
!
k
!
=
p
⋅
(
p
−
1
)
⋯
(
p
−
k
+
1
)
k
!
其
中
因
为
C
p
k
∈
N
，
所
以
k
!
∣
(
p
⋅
(
p
−
1
)
⋯
(
p
−
k
+
1
)
)
，
同
时
因
为
0
<
k
<
p
，
所
以
g
c
d
(
k
!
,
p
)
=
1
，
即
k
!
∣
(
p
−
1
)
⋯
(
p
−
k
+
1
)
，
即
p
∣
C
p
k
，
然
后
我
们
将
上
面
二
项
式
展
开
公
式
进
行
m
o
d
2
的
处
理
，
化
简
为
:
a
p
m
o
d
p
=
(
∑
k
=
0
p
C
p
k
1
(
p
−
k
)
)
m
o
d
p
a
p
m
o
d
p
≡
1
+
(
a
−
1
)
)
p
(
m
o
d
m
)
上
面
我
们
将
a
p
拆
分
成
(
1
+
(
a
−
1
)
)
p
，
那
么
是
不
是
同
样
可
以
拆
分
成
(
2
+
(
a
−
2
)
)
p
(
3
+
(
a
−
3
)
)
p
⋮
(
a
+
(
a
−
a
)
)
p
最
终
递
归
得
出
a
p
≡
a
(
m
o
d
p
)
a^p=(1+(a-1))^p= \\ \sum^{p}_{k=0} {C}^{k}_{p} {1}^{(p-k)} {(a-1)}^{k},{C}^{k}_{p}=\frac{p!}{(p-k)!k!}=\frac{p \cdot (p-1) \cdots (p-k+1)}{k!} \\ 其中因为 {C}^{k}_{p} \in N，所以 k!|(p \cdot (p-1) \cdots (p-k+1))，同时因为0<k<p，所以 gcd(k!,p)=1，即\\ k!|(p-1)\cdots (p-k+1)，即\\ p|{C}^{k}_{p}，然后我们将上面二项式展开公式进行 mod 2的处理，化简为:\\ a^p \mod p =(\sum^{p}_{k=0} {C}^{k}_{p} {1}^{(p-k)}) \mod p \\ a^p \mod p \equiv 1+(a-1))^p (mod\ m) \\ 上面我们将 a^p 拆分成 (1+(a-1))^p，那么是不是同样可以拆分成 \\ (2+(a-2))^p\\ (3+(a-3))^p\\ \vdots (a+(a-a))^p\\ 最终递归得出 \\ a^p \equiv a (mod\ p)
ap=(1+(a−1))p=k=0∑pCpk1(p−k)(a−1)k,Cpk=(p−k)!k!p!=k!p⋅(p−1)⋯(p−k+1)其中因为Cpk∈N，所以k!∣(p⋅(p−1)⋯(p−k+1))，同时因为0<k<p，所以gcd(k!,p)=1，即k!∣(p−1)⋯(p−k+1)，即p∣Cpk，然后我们将上面二项式展开公式进行mod2的处理，化简为:apmodp=(k=0∑pCpk1(p−k))modpapmodp≡1+(a−1))p(mod m)上面我们将ap拆分成(1+(a−1))p，那么是不是同样可以拆分成(2+(a−2))p(3+(a−3))p⋮(a+(a−a))p最终递归得出ap≡a(mod p)
参考B站视频
伪素数
简单来说就是，以前的中国人认为
如
果
n
为
奇
数
，
且
满
足
下
面
的
公
式
时
2
n
−
1
≡
1
(
m
o
d
n
)
，
n
即
为
素
数
。
如果n为奇数，且满足下面的公式时 {2}^{n-1} \equiv 1 (mod\ n)，n即为素数。
如果n为奇数，且满足下面的公式时2n−1≡1(mod n)，n即为素数。
但是这个结论是错误的，而能推翻上面的数，就称为伪素数。比如
2
341
−
1
≡
1
(
m
o
d
341
)
但
是
341
=
11
⋅
31
，
其
并
不
是
素
数
{2}^{341-1} \equiv 1 (mod\ 341) \\ 但是 341=11 \cdot 31，其并不是素数
2341−1≡1(mod 341)但是341=11⋅31，其并不是素数
卡米切尔数
首 先 是 一 个 正 整 数 n ， 然 后 是 所 有 与 n 互 质 的 数 b ， 都 满 足 b n − 1 ≡ 1 ( m o d n ) 则 这 样 的 n 就 称 为 卡 米 切 尔 数 首先是一个正整数n，然后是所有与n互质的数b，都满足\\ {b}^{n-1} \equiv 1 (mod\ n) \\ 则这样的n就称为卡米切尔数 首先是一个正整数n，然后是所有与n互质的数b，都满足bn−1≡1(mod n)则这样的n就称为卡米切尔数
原根和离散对数
原根
设
定
两
个
数
，
x
和
y
，
x
,
y
∈
Z
，
x
为
素
数
，
如
果
对
于
从
0
开
始
，
到
x
−
1
中
的
每
一
个
正
整
数
，
假
设
为
k
，
都
有
x
k
m
o
d
y
=
k
0
，
其
中
所
有
k
0
的
值
正
好
满
足
1
到
y
−
1
时
，
则
称
x
是
y
的
原
根
设定两个数，x和y，x,y \in Z，x为素数，如果对于从0开始，到x-1中的每一个正整数，假设为k，都有 \\ {x}^{k} mod\ y={k}_{0}，其中所有{k}_{0}的值正好满足 1到y-1时，则称x是y的原根
设定两个数，x和y，x,y∈Z，x为素数，如果对于从0开始，到x−1中的每一个正整数，假设为k，都有xkmod y=k0，其中所有k0的值正好满足1到y−1时，则称x是y的原根
例如x为2，y是11：
2
1
m
o
d
11
=
2
2
2
m
o
d
11
=
4
2
3
m
o
d
11
=
8
2
4
m
o
d
11
=
5
2
5
m
o
d
11
=
10
2
6
m
o
d
11
=
9
2
7
m
o
d
11
=
7
2
8
m
o
d
11
=
3
2
9
m
o
d
11
=
6
2
10
m
o
d
11
=
1
满
足
1
到
10
，
所
以
2
是
11
的
原
根
2^1 \mod 11=2 \\ 2^2 \mod 11=4 \\ 2^3 \mod 11=8 \\ 2^4 \mod 11=5 \\ 2^5 \mod 11=10 \\ 2^6 \mod 11=9 \\ 2^7 \mod 11=7 \\ 2^8 \mod 11=3 \\ 2^9 \mod 11=6 \\ {2}^{10} \mod 11=1 \\ 满足 1 到 10，所以2是11的原根
21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=1满足1到10，所以2是11的原根
离散对数
在
上
面
原
根
的
基
础
上
，
假
设
a
是
介
于
0
到
y
−
1
之
间
的
一
个
整
数
，
则
存
在
一
个
整
数
e
，
使
得
x
e
m
o
d
y
=
a
，
此
时
，
我
们
称
e
为
以
x
为
底
，
a
模
y
的
离
散
对
数
，
写
作
l
o
g
x
a
=
e
在上面原根的基础上，假设 a 是介于0到y-1之间的一个整数，则存在一个整数e，使得 \\ {x}^{e} \mod y =a，此时，我们称e为以x为底，a模y的离散对数，写作 \\ {log}_{x} a =e
在上面原根的基础上，假设a是介于0到y−1之间的一个整数，则存在一个整数e，使得xemody=a，此时，我们称e为以x为底，a模y的离散对数，写作logxa=e
注意：在上面的表示法中，没有展示y的值。