贵阳公司官方网站建设,wordpress按分类搜索,河南网站建设SEO优化制作设计公司,如何检测网站是否安全孙子定理和“物不知数”问题
孙子定理#xff0c;也称为中国剩余定理或中国余数定理。孙子定理是中国古代求解一次同余式组#xff08;见同余#xff09;的方法。此定理#xff0c;在公元5-6世纪的中国南北朝时期的数学家孙子提出的“物不知数”问题可以被视为中国剩余定…孙子定理和“物不知数”问题
孙子定理也称为中国剩余定理或中国余数定理。孙子定理是中国古代求解一次同余式组见同余的方法。此定理在公元5-6世纪的中国南北朝时期的数学家孙子提出的“物不知数”问题可以被视为中国剩余定理的一个应用实例。
《孙子算经》卷下第二十六题叫做“物不知数”问题原文如下
有物不知其数三三数之剩二五五数之剩三七七数之剩二。问物几何即一个整数除以三余二除以五余三除以七余二求这个整数。
宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。
解一
采用通用的方法逐步满足法
七七数之剩二即除以7余2的数可以写成7n2从小到大排列9162331……
然后从小到大找除以3余2的三三数之剩二和以5余3的五五数之剩三的数发现最小的是23.
所以23就是所求的数。
先满足一个条件再满足另一个条件所以称之为“逐步满足法”。 解二
可以使用孙子定理中国剩余定理来解决这个问题
先简要介绍中国剩余定理下面用现代数学的语言来说明。
假设有如下的一组线性同余方程
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
…
x ≡ an (mod mn)
其中m1 m2 … mn是两两互质的正整数a1 a2 … an是整数求解这样的一组线性同余方程的一般公式如下
x (Σ(ai × Mi × ti)) mod M
其中M m1 × m2 × … × mnMi M ÷ miti是Mi对mi的模逆元即满足(Mi × ti) ≡ 1 (mod mi)的整数。
模逆元也称为模反元素假设有一个整数a和一个模m如果存在一个整数b使得ab ≡ 1 (mod m)那么我们就称b是a关于模m的模逆元或者模反元素。
关于孙子定理详情可见孙子定理_百度百科
下面使用孙子定理来解决这个问题
设这个整数为x。根据题目的条件我们可以列出以下同余方程组
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
在这个问题中a1, a2, a3分别代表的是每个同余方程的模余数即a1 2, a2 3, a3 2。
首先计算所有模数的乘积M 3 × 5 × 7 105
然后为每个方程计算Mi即模数乘积除以对应的模数
M1 M ÷ 3 35
M2 M ÷ 5 21
M3 M ÷ 7 15
接下来我们需要计算每一个模逆元ti 即满足(Mi × ti) ≡ 1 (mod mi)的整数
对于M1我们有 (35 × 2) mod 3 1所以t1 2
对于M2我们有 (21 × 1) mod 5 1所以t2 1
对于M3我们有 (15 × 1) mod 5 1所以t3 1
【注具体说来对于M135我们需要找到一个数 (35 × t1) mod 3 1。通过尝试我们发现t1 2可以满足这个等式因为 (35 × 2) mod 3 70 mod 3 1。所以在这个情况下我们说2就是35关于模3的模逆元。
在更复杂的问题中尝试所有可能的整数可能是不现实的。这时我们可以使用扩展欧几里得算法来高效地计算模逆元这是一个更高级的主题。】
最后我们将计算得到的结果带入到中国剩余定理的公式中
x (a1 × M1 × t1 a2 × M2 × t2 a3 × M3 × t3) mod M (2 × 35 × 2 3 × 21 × 1 2 × 15 × 1) (mod 105) (140 63 30) (mod 105) 23 (mod 105)
因此物的数目为23。
