模运算中解同余方程的经典方法
1 简介
解同余方程即“大衍求一术”是中国古代数学经典《孙子算经》中提出的一种**解同余方程(一次中国剩余定理)**的方法,用于求解一个未知数在多个模数下的同余关系。这种方法可以说是古代中国对现代数论(模运算)的一种朴素而精妙的实现。
问题的提出:
某实验室有一袋粉末物品重量未知,有一个最大称重300克的电子秤,
有天平砝码3类,分别做以下操作:
使用300克砝码称重该商品余200克,
使用500克砝码称重该商品余300克,
使用700克砝码称重该商品余200克,
该商品总重量多少?
为了方便计算,描述为 求一个数 x,使得:
x≡2(mod3)
x≡3(mod5)
x≡2(mod7)
2 古法大衍求一术的步骤
举例说明“大衍求一术”的计算步骤
我们用“大衍求一术”来解这个问题。
- 古法
其实就是通过构造一组系数,使得最终构成满足条件的最小自然数解。我们简化为现代记法来解释原理。
第一步:设模数
m1=3,m2=5,m3=7
设总体模数
M=m1*m2*m3=3×5×7=105
第二步:分别求:
M1=M/m1=105/3=35
M2=105/5=21
M3=105/7=15
第三步:求逆元(使得𝑀𝑖⋅𝑦𝑖≡1(mod𝑚𝑖))
35⋅y1≡1(mod3)⇒y1=2 (因为 35×2=70≡1(mod3))
21⋅𝑦2≡1(mod5)⇒𝑦2=1 (21%5 = 1 这里%表示取余)
15⋅𝑦3≡1(mod7)⇒𝑦3=1 (15%7 = 1 这里%表示取余)
第四步:构造解:
𝑥=(𝑎1⋅𝑀1⋅𝑦1)+(𝑎2⋅𝑀2⋅𝑦2)+(𝑎3⋅𝑀3⋅𝑦3)mod𝑀
代入各值:
x=(2⋅35⋅2)+(3⋅21⋅1)+(2⋅15⋅1)=140+63+30=233
取模:
x≡233mod105⇒x=233mod105= 23
即233除以105的余数为23
233 % 105 = 23
3 现代代数系统计算步骤
- 现代代数方法(线性同余方程)
现代代数中我们会直接调用中国剩余定理(CRT),它与“大衍求一术”本质上是一样的,只是现代数学用线性代数和模反元素定义得更严密。
主要区别:
比较维度 大衍求一术 现代代数方法
起源 中国《孙子算经》 西方近代代数学体系
形式 算筹算法,口算或笔算 使用模反元素、符号系统化
表达方式 自然语言与算法结合 使用代数符号、公式推导
使用工具 乘除、辗转求逆 拓展欧几里得算法等
现代方法使用模反元素与线性代数技巧一步一步解一个包含三个模的同余方程组,使用中国剩余定理(CRT)的标准方法。
问题:
解下面的同余方程组:
x≡2(mod3)
x≡3(mod5)
x≡2(mod7)
这三个模数 3,5,7 两两互素,可以直接用中国剩余定理求解。
总公式
𝑀x=a1M1y1 + a2M2y2 + a3M3y3
已知 a1 = 2, a2=3, a3=2 需要分别计算 M1,M2,M3,和 y1,y2,y3
步骤 1:计算总模数
M=3x5x7=105
步骤 2:计算每一项的乘余积
M1=105/3=35
M2=105/5=21
M3=105/7=15
步骤 3:求模逆元
𝑦𝑖,使得:
𝑀𝑖⋅𝑦𝑖≡1(mod_𝑚𝑖)
我们要找:
- y1
35⋅𝑦1≡1(mod3)
35≡1(mod3)
所以 2⋅y1 ≡1(mod3) ⇒y1=2
- y2
21⋅y2≡1(mod5)
21≡1(mod5)
所以 1⋅y2≡1 ⇒y2=1
- y3
15⋅y3≡1(mod7)
15≡1(mod7) ⇒y3=1
步骤 4:代入总公式
𝑀x=a1M1y1 + a2M2y2 + a3M3y3
modM代入:
x=2⋅35⋅2+3⋅21⋅1+2⋅15⋅1
x=140+63+30=233
最后取模:
x≡233mod105 ⇒ x≡23
-
最终解:
x≡23(mod105)
也就是说,所有满足这个同余方程组的解是:
x=23+105k,k∈Z
4 小结
“大衍求一术”与现代代数中国剩余定理完全等价,是其早期形式。
古人采用实际数值、递推方式来寻找解,而现代方法使用模反元素与线性代数技巧,但本质目标和结构是一样的。
- 点赞
- 收藏
- 关注作者
评论(0)