中国剩余定理
中国剩余定理
一、问题的引入
-
一个整数除以3余2、除以5余3、除以7余2，求这个整数？答案：23
-
所谓中国剩余定理基本思想：知道一个整数对于几个不同的模数的余数，那么可以推断出该整数对于这些模数的最小非负整数解。
二、拓展欧几里得求逆元
逆元定义：如果一个线性同余方程 a x ≡ 1 ? ( m o d ? b ) ax \equiv 1 \ (mod\ b) ax≡1?(mod?b)则称 x 为 a ? m o d ? b a\ mod \ b a?mod?b 的逆元，记作 a ? 1 a^{-1} a?1
拓展欧几里得算法核心方程：
a
x
+
b
y
=
d
=
g
c
d
(
a
,
b
)
ax + by = d = gcd(a,b)
ax+by=d=gcd(a,b)
根据逆元等式：
a
x
≡
1
(
?
m
o
d
??
b
)
?
[
此时
a
、
b
为已知量
,
x
为
a
的逆元
a
?
1
]
转化??
a
x
≡
1
(
?
m
o
d
??
b
)
?
?
【
a
x
=
n
b
+
1
】
?
【
a
x
+
n
′
b
=
1
】
(
n
=
?
n
′
)
\begin{align*} & 根据逆元等式：ax\equiv 1(\ mod\ \ b)\ [此时a、b为已知量,x为a的逆元a^{-1}]\\ & 转化\ \ ax\equiv 1(\ mod\ \ b)\ \Longrightarrow 【ax = nb + 1】\Longrightarrow【ax + n'b = 1】(n = -n') & \end{align*}
?根据逆元等式：ax≡1(?mod??b)?[此时a、b为已知量,x为a的逆元a?1]转化??ax≡1(?mod??b)??【ax=nb+1】?【ax+n′b=1】(n=?n′)??
将上述逆元的定义方程进行转化后我们来对比转化方程与拓展欧几里得核心方程
(
1
)
a
x
+
b
n
=
1
【逆元转化方程】
(
2
)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
【拓展欧几里得核心方程】
\begin{align*} & (1){\color{red}a}x + {\color{red}b}n = 1 【逆元转化方程】\\ & (2){\color{red}a}x + {\color{red}b}y = gcd(a,b) 【拓展欧几里得核心方程】\\ \end{align*}
?(1)ax+bn=1【逆元转化方程】(2)ax+by=gcd(a,b)【拓展欧几里得核心方程】?
可以看到上述两方程的格式不能说相似，只能说一模一样。只需要使用拓展欧几里得算法对互质的两个数求出一组解
(
x
,
y
)
(x,y)
(x,y)
就可以获得逆元了。
三、中国剩余定理的原理
我们继续考虑上述问题：
求整数
X
除以
3
余
2
、除以
5
余
3
、除以
7
余
2
。转化为下述公式
:
X
??
%
??
3
?
=
?
2
X
??
%
??
5
?
=
?
3
X
??
%
??
7
?
=
?
2
求整数X除以3余2、除以5余3、除以7余2。转化为下述公式: \\ X\ \ \% \ \ 3\ =\ 2\\ X\ \ \% \ \ 5\ =\ 3\\ X\ \ \% \ \ 7\ =\ 2\\
求整数X除以3余2、除以5余3、除以7余2。转化为下述公式:X??%??3?=?2X??%??5?=?3X??%??7?=?2
如果可以找到三个整数
X
1
、
X
2
、
X
3
X_1、X_2、X_3
X1?、X2?、X3? 并且满足下述的算式
{
X
1
?
%
?
3
=
2
X
1
?
%
?
5
=
0
X
1
?
%
?
7
=
0
{
X
2
?
%
?
3
=
0
X
2
?
%
?
5
=
3
X
2
?
%
?
7
=
0
{
X
3
?
%
?
3
=
0
X
3
?
%
?
5
=
0
X
3
?
%
?
7
=
2
\left\{ \begin{array}{lr} X_1\ \% \ 3 = 2 \\ X_1\ \% \ 5 = 0 \\ X_1\ \% \ 7 = 0 \\ \end{array} \right. \qquad \qquad \left\{ \begin{array}{lr} X_2\ \% \ 3 = 0 \\ X_2\ \% \ 5 = 3 \\ X_2\ \% \ 7 = 0 \\ \end{array} \right. \qquad \qquad \left\{ \begin{array}{lr} X_3\ \% \ 3 = 0 \\ X_3\ \% \ 5 = 0 \\ X_3\ \% \ 7 = 2 \\ \end{array} \right.
?
?
??X1??%?3=2X1??%?5=0X1??%?7=0??
?
??X2??%?3=0X2??%?5=3X2??%?7=0??
?
??X3??%?3=0X3??%?5=0X3??%?7=2?
那么
X
X
X 可以由这三个整数
X
1
、
X
2
、
X
3
X_1、X_2、X_3
X1?、X2?、X3? 构成
X
=
X
1
+
X
2
+
X
3
X = X_1 + X_2 + X_3
X=X1?+X2?+X3?
继续将上述的
X
1
、
X
2
、
X
3
X_1、X_2、X_3
X1?、X2?、X3? 分解为子问题
{
Y
1
?
%
?
3
=
1
Y
1
?
%
?
5
=
0
Y
1
?
%
?
7
=
0
{
Y
2
?
%
?
3
=
0
Y
2
?
%
?
5
=
1
Y
2
?
%
?
7
=
0
{
Y
3
?
%
?
3
=
0
Y
3
?
%
?
5
=
0
Y
3
?
%
?
7
=
1
\left\{ \begin{array}{lr} Y_1\ \% \ 3 = 1 \\ Y_1\ \% \ 5 = 0 \\ Y_1\ \% \ 7 = 0 \\ \end{array} \right. \qquad \qquad \left\{ \begin{array}{lr} Y_2\ \% \ 3 = 0 \\ Y_2\ \% \ 5 = 1 \\ Y_2\ \% \ 7 = 0 \\ \end{array} \right. \qquad \qquad \left\{ \begin{array}{lr} Y_3\ \% \ 3 = 0 \\ Y_3\ \% \ 5 = 0 \\ Y_3\ \% \ 7 = 1 \\ \end{array} \right.
?
?
??Y1??%?3=1Y1??%?5=0Y1??%?7=0??
?
??Y2??%?3=0Y2??%?5=1Y2??%?7=0??
?
??Y3??%?3=0Y3??%?5=0Y3??%?7=1?
于是
X
1
、
X
2
、
X
3
X_1、X_2、X_3
X1?、X2?、X3? 就可以由对应的Y构成
X
1
?
=
?
2
?
Y
1
X
2
?
=
?
3
?
Y
2
X
3
?
=
?
2
?
Y
3
X_1\ =\ 2\ Y_1\\ X_2\ =\ 3\ Y_2\\ X_3\ =\ 2\ Y_3\\
X1??=?2?Y1?X2??=?3?Y2?X3??=?2?Y3?
所以根据上述的分解，我们最后得到了
?
X
?
=
?
2
?
Y
1
+
3
?
Y
2
+
2
?
Y
3
\ X \ = \ 2\ Y_1 + 3\ Y_2 + 2\ Y_3
?X?=?2?Y1?+3?Y2?+2?Y3?
我们以其中一个子问题为例求解
Y
1
?
%
?
3
=
1
Y
1
?
%
?
5
=
0
Y
1
?
%
?
7
=
0
Y_1\ \% \ 3 = 1 \\ Y_1\ \% \ 5 = 0 \\ Y_1\ \% \ 7 = 0 \\
Y1??%?3=1Y1??%?5=0Y1??%?7=0
根据上述等式不难知道
Y
1
Y_1
Y1? 一定是
5
×
7
=
35
5 \times 7 = 35
5×7=35 的倍数，于是我们令
Y
1
=
35
k
Y_1 = 35 k
Y1?=35k
那么就有 35 k ≡ 1 ( m o d 3 ) 35k \equiv 1 \pmod{3} 35k≡1(mod3)，这时 k k k 就是 5 × 7 5 \times 7 5×7 模 3 的逆元，记 k = [ 3 5 ? 1 ] 3 k = [35^{-1}]_3 k=[35?1]3? 那么 Y 1 = 5 × 7 × [ 3 5 ? 1 ] 3 Y_1 = 5 \times 7\times [35^{-1}]_3 Y1?=5×7×[35?1]3?
因此将所有子问题求解得下述等式
{
Y
1
=
5
×
7
×
[
(
5
×
7
)
?
1
]
3
并且
[
(
5
×
7
)
?
1
]
3
=
2
Y
2
=
3
×
7
×
[
(
3
×
7
)
?
1
]
5
并且
[
(
3
×
7
)
?
1
]
5
=
1
Y
3
=
3
×
5
×
[
(
3
×
5
)
?
1
]
7
并且
[
(
3
×
5
)
?
1
]
7
=
1
\left\{ \begin{array}{lr} Y_1 = 5 \times 7\times [(5\times7)^{-1}]_3\qquad 并且[(5\times7)^{-1}]_3 = 2\\ Y_2 = 3 \times 7\times [(3\times7)^{-1}]_5\qquad 并且[(3\times7)^{-1}]_5 = 1\\ Y_3 = 3 \times 5\times [(3\times5)^{-1}]_7\qquad 并且[(3\times5)^{-1}]_7 = 1\\ \end{array} \right.
?
?
??Y1?=5×7×[(5×7)?1]3?并且[(5×7)?1]3?=2Y2?=3×7×[(3×7)?1]5?并且[(3×7)?1]5?=1Y3?=3×5×[(3×5)?1]7?并且[(3×5)?1]7?=1?
由此可以得到最终式子还要mod
(
3
×
5
×
7
)
(3\times5\times7)
(3×5×7)因为要求最小整数
X
=
2
×
(
5
×
7
×
[
(
5
×
7
)
?
1
]
3
)
+
3
×
(
3
×
7
×
[
(
3
×
7
)
?
1
]
5
)
+
2
×
(
3
×
5
×
[
(
3
×
5
)
?
1
]
7
)
(
m
o
d
3
×
5
×
7
)
X = 2\times (5 \times 7\times [(5\times7)^{-1}]_3) + 3\times(3 \times 7\times [(3\times7)^{-1}]_5) + 2\times(3 \times 5\times [(3\times5)^{-1}]_7) \pmod{3\times5\times7}\\
X=2×(5×7×[(5×7)?1]3?)+3×(3×7×[(3×7)?1]5?)+2×(3×5×[(3×5)?1]7?)(mod3×5×7)
逆元怎么求？看上述第二节的内容
[
(
5
×
7
)
?
1
]
3
=
2
[
(
3
×
7
)
?
1
]
5
=
1
[
(
3
×
5
)
?
1
]
7
=
1
[(5\times7)^{-1}]_3 = 2\\ [(3\times7)^{-1}]_5 = 1\\ [(3\times5)^{-1}]_7 = 1\\
[(5×7)?1]3?=2[(3×7)?1]5?=1[(3×5)?1]7?=1
所以
X
=
(
2
×
5
×
7
×
2
)
+
(
3
×
3
×
7
×
1
)
+
(
2
×
3
×
5
×
1
)
(
m
o
d
105
)
=
(
140
+
63
+
30
)
(
m
o
d
105
)
=
23
\color{blue}X = (2 \times 5 \times 7 \times 2) + (3\times3\times7\times1) + (2\times3\times5\times1) \pmod{105} = (140+63+30)\pmod{105} = 23
X=(2×5×7×2)+(3×3×7×1)+(2×3×5×1)(mod105)=(140+63+30)(mod105)=23
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！