[原创]有关同余式的问题

mathck

[watermark]数论概论（原书第3版）： Joseph H. Silverman著，孙智伟等译
第8章 同余式，第34页，倒数第7行，例子如下：
893x = 266(mod 2432)
书中的说法是将上面的方程转化为: 893u- 2432v= 19。然后，按照第6章的方法，求得(u,v)为（79,29）.......
----------
我的问题是：
----------
我按照第6章的方法，计算得结果是(u,v)为（18，49），与上面的结果不一样。但我检查了很久，也没有发现问题出在哪里。具体的计算过程如下：
gcd(893, 2432)的过程如下：
1) 646= 2432 - 893 * 2
2) 247= 893 - 646 * 1
3) 152 = 646 - 247 * 2
4) 95= 247 - 152 * 1
5) 57= 152 - 95 * 1
6) 38 = 95 - 57 * 1
7) 19= 57 - 38 * 1
8) 0= 38 - 19 * 2
现在假设 a = 2432, b = 893，则上面的 1）~7） 会变为如下：
1) 646= a - 2b
2) 247= 3b - a
3) 152= 3a - 8b
4) 95= 11b - 4a
5) 57= 7a - 19b
6) 38= 30b - 11a
7) 19= 18a - 49b
所以，(u,v) 为 （18，49）。
是否我算错了？如果是的话，错在哪里？[/watermark]

mathck

有人知道吗？。。。。。。。。。。

fungarwai

(u,v)=(-49,-18)也没错
答案可以是(79+128k,29+47k)
这种问题是可以用矩阵解的，参见：
https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95

mathck

下面引用由fungarwai在 2014/04/20 04:51pm 发表的内容：
(u,v)=(-49,-18)也没错
答案可以是(79+128k,29+47k)
这种问题是可以用矩阵解的，参见：
https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95

楼上，为何是（-49，-18）？ 此外，（79，29）是如何计算出来的？可否简单列个过程？谢谢。

fungarwai

你的18,49这两个值是算对的，不需要在乎那个79,29
其实893和2432都整除19，把它除掉算了
47u-128v=1

这样也得到47(-49)+128(18)=1
因为47(128)-128(47)=0，所以会造成无穷多个解

mathck

[这个贴子最后由mathck在 2014/04/23 02:58pm 第 2 次编辑]

楼上，
谢谢你的回复。我总结了一下，对于求解同余式 893x = 266(mod 2432)，步骤如下：
[color=#0000FF]第一步：确定该同余式是否有解，如果有，有多少个解？
方法是求 893 与 2432 的最大公因数，即 g = gcd(893, 2432)。如果 g 整除 266，则同余式有解，且解的个数为g；否则，同余式无解。
而计算最大公因数的方法在第6章已有介绍，具体如下：
gcd(893, 2432)的过程如下：
1) 646= 2432 - 893 * 2
2) 247= 893 - 646 * 1
3) 152 = 646 - 247 * 2
4) 95= 247 - 152 * 1
5) 57= 152 - 95 * 1
6) 38 = 95 - 57 * 1
7) 19= 57 - 38 * 1
8) 0= 38 - 19 * 2
可见， g=19，且 g | 266，即同余式有解，且解的个数为19

[color=#0000FF]第二步：从第一步可知，同余式有19个解，但这些解都是多少，目前并不知道（即要求 x0 ~ x18）。在求 x0 ~x18 的过程里，要用到 （u0, v0），因为书中第34页里、第5行里已定义 x0 = c*u0/g(mod m)。因此，这一步要做的就是求（u0,v0）。
而求（u0, v0）的关键是求解线性方程 893u + 2432v = gcd(893, 2432) = 19（即第6章中提到的 au + mv = g）。
现在假设 a = 2432, b = 893，根据第一步里的 1）~7），可得：
1) 646= a - 2b
2) 247= 3b - a
3) 152= 3a - 8b
4) 95= 11b - 4a
5) 57= 7a - 19b
6) 38= 30b - 11a
7) 19= 18a - 49b
由上可得，u0=-49, v0=18(因为 18*2432 + (-49)*893 = 19).

[color=#0000FF]第三步：从第一步可知同余式有19个解，由第二步可知每个解所需的（u0,v0)（即（-49,18）），则第一个解为：
x0 = c*u0/g(mod m) = 266 * (-49) / 19(mod 2432) = -686(mod 2432)。
其余的解为：
Xk = x0 + k * m /g(mod 2432) = -686 + 128k(mod 2432)， 0 < k < 19

[color=&#35;0000FF]
========
问题：
========
1、以上整个的解题过程对吗？也就是解题的思路对吗？
2、-686的这个值是个负数，这个值是否正确？
3、为何 x0 是等于 c*u0/g(mod m)？
注：在书中第34页第一行， au + mv = g，两边乘以 c/g，得 a * u0 * c/g + m * v0 * c/g = c，因此书中认为 x0 是等于c*u0/g(mod m)。但为何要乘以 c/g 呢？为何x0 不能等于 u0（即在不乘以 c/g 的前提下）或取其他值？

mathck

有人知道吗？

fungarwai

明白同余方程的本质就可以了
893x≡266(mod2432)→893x+2432k=266
47x+128k=14→47x≡14(mod128)
47(-49)+128(18)=1
47x≡14(mod128)
47(-49)x≡14(-49)(mod128)
[47(-49)+128(18)]x≡14(-49)(mod128)
x≡14(-49)≡-686(mod128)
x≡-686(mod128)→x=128k-686
例如x≡2(mod3)意味着对于任何整数k有x+3k=2
x也可以是-1,-4,-7,...这些负整数

mathck

下面引用由fungarwai在 2014/04/23 09:31pm 发表的内容：
明白同余方程的本质就可以了
893x≡266(mod2432)→893x+2432k=266
47x+128k=14→47x≡14(mod128)
47(-49)+128(18)=1
...

但是对于 x0 的计算呢？即，为何 x0 是等于 c*u0/g(mod m)？ 为何 x0 不能等于 u0 或者其他数？

fungarwai

只是一开始没有把19除掉，最后要把19除掉而已
你要把它当成一般方程来看
19x0≡266(-49)(mod2432)→19x0+2432k=266(-49)