模运算中解同余方程的经典方法

举报
码乐 发表于 2025/07/02 09:51:01 2025/07/02
【摘要】 1 简介解同余方程即“大衍求一术”是中国古代数学经典《孙子算经》中提出的一种**解同余方程(一次中国剩余定理)**的方法,用于求解一个未知数在多个模数下的同余关系。这种方法可以说是古代中国对现代数论(模运算)的一种朴素而精妙的实现。问题的提出: 某实验室有一袋粉末物品重量未知,有一个最大称重300克的电子秤, 有天平砝码3类,分别做以下操作: 使用300克砝码称重该商品余200克, ...

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 小结

“大衍求一术”与现代代数中国剩余定理完全等价,是其早期形式。
古人采用实际数值、递推方式来寻找解,而现代方法使用模反元素与线性代数技巧,但本质目标和结构是一样的。

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。