Home
/
Math
/
Modular Arithmetic
Search
Try Notion
Modular Arithmetic
概念:
若有
a
%
m
=
b
%
m
则整数
a
与
b
对模
m
同余
,
记作
a
≡
b
(
m
o
d
m
)
若有a\%m=b\%m则整数a与b对模m同余,记作a≡b(mod\; m)
若有
a
%
m
=
b
%
m
则整数
a
与
b
对模
m
同余
,
记作
a
≡
b
(
m
o
d
m
)
性质
满足等价关系
Liner Agerbra
加法\乘法
若有
a
≡
b
(
m
o
d
m
)
c
≡
d
(
m
o
d
m
)
a\equiv b(\ mod \ m) \quad c\equiv d (\ mod \ m \ )
a
≡
b
(
m
o
d
m
)
c
≡
d
(
m
o
d
m
)
则有以下运算律
(
a
±
c
)
≡
(
b
±
d
)
(
m
o
d
m
)
(a\pm c)\equiv (b \pm d) (\ mod \ m)
(
a
±
c
)
≡
(
b
±
d
)
(
m
o
d
m
)
(
a
c
)
≡
(
b
d
)
(
m
o
d
m
)
(ac)\equiv (bd) (\ mod \ m)
(
a
c
)
≡
(
b
d
)
(
m
o
d
m
)
推论1:由自反性可得两边加减或乘上任意数同余方程依旧成立
除法性质
若有
(
a
c
)
≡
(
c
d
)
(
m
o
d
m
)
(ac)\equiv (cd) (\ mod \ m)
(
a
c
)
≡
(
c
d
)
(
m
o
d
m
)
则有
a
≡
b
(
m
o
d
m
g
c
d
(
m
,
c
)
)
a \equiv b \ (mod \ \frac{m}{gcd(m,c)})
a
≡
b
(
m
o
d
g
c
d
(
m
,
c
)
m
)
证明
由
(
a
c
)
≡
(
c
d
)
(
m
o
d
m
)
可得
a
c
=
c
d
+
k
m
同除
c
得
a
=
d
+
m
k
c
若有
m
k
∣
c
则才能讨论余数问题
显然可将其化为两个整数
m
g
c
d
(
c
,
m
)
=
n
k
∗
g
c
d
(
c
,
m
)
c
=
k
′
保证当
m
k
/
c
=
n
k
′
时候
n
取最小
k
取最大
则有
a
≡
b
(
m
o
d
m
g
c
d
(
m
,
c
)
)
由(ac)\equiv (cd) (\ mod \ m) \\可得ac=cd+km \\ 同除c得 a=d+\frac{mk}{c} \\若有mk|c则才能讨论余数问题\\显然可将其化为两个整数\frac{m}{gcd(c,m)}=n \quad \frac{k*gcd(c,m)}{c}=k' 保证当mk/c=nk'时候n取最小k取最大 \\则有a \equiv b \ (mod \ \frac{m}{gcd(m,c)})
由
(
a
c
)
≡
(
c
d
)
(
m
o
d
m
)
可得
a
c
=
c
d
+
km
同除
c
得
a
=
d
+
c
mk
若有
mk
∣
c
则才能讨论余数问题
显然可将其化为两个整数
g
c
d
(
c
,
m
)
m
=
n
c
k
∗
g
c
d
(
c
,
m
)
=
k
′
保证当
mk
/
c
=
n
k
′
时候
n
取最小
k
取最大
则有
a
≡
b
(
m
o
d
g
c
d
(
m
,
c
)
m
)
