数学建模社区-数学中国
标题:
有关同余式的问题
[打印本页]
作者:
mathtin
时间:
2014-4-20 15:59
标题:
有关同余式的问题
数论概论（原书第3版）： Joseph H. Silverman著，孙智伟等译
' V" y7 n0 N8 Y6 O2 d2 m
$ D7 W7 O: h1 m2 p0 P
第8章 同余式，第34页，倒数第7行，例子如下：
2 n9 `9 D, Q( E2 Y& d( ]8 o
8 |. P4 n0 k# {
893x = 266(mod 2432)
: D1 `5 q" _; o
& D: V8 E1 v2 W0 x: I
书中的说法是将上面的方程转化为: 893u- 2432v= 19。然后，按照第6章的方法，求得(u,v)为（79,29）.......
+ t% f* t T6 h7 a: s
3 @" o- G* K6 A$ J' r
----------
4 p3 w; j9 B% m6 S" ?
我的问题是：
5 s6 l% H8 g" q% v1 @6 z
----------
3 C. K3 F- x% I/ _$ r$ Y6 t+ ^5 i
我按照第6章的方法，计算得结果是(u,v)为（18，49），与上面的结果不一样。但我检查了很久，也没有发现问题出在哪里。具体的计算过程如下：
9 z o& N$ O3 w
" |/ Y: f; j' _3 b* M5 P) z5 E* Y
gcd(893, 2432)的过程如下：
. z& m$ D7 U r3 o: [% l
! u7 D+ r6 U! E5 t9 R& {
1) 646 = 2432 - 893 * 2
4 X/ a$ o/ ^6 c: G
2) 247 = 893 - 646 * 1
1 y" j: i1 s" ~* q5 m
3) 152 = 646 - 247 * 2
9 q& E( f' s- H( a& H) @% E& L
4) 95 = 247 - 152 * 1
3 G) f1 z" z+ }8 C# t& S N
5) 57 = 152 - 95 * 1
* j* V/ @. [3 C+ Y, x, \
6) 38 = 95 - 57 * 1
' ^# r E9 n1 Q; ?6 M$ J- g
7) 19 = 57 - 38 * 1
( ?1 \$ Q, q# z( q9 f. g& E" u
8) 0 = 38 - 19 * 2
' S! G: }7 v. M0 f D
9 C- Y# s3 }, A
现在假设 a = 2432, b = 893，则上面的 1）~7） 会变为如下：
0 I5 W# ?/ _+ B4 X, F2 [ o) k
) {# z/ L! L; [+ ~* E2 M
1) 646 = a - 2b
1 B$ J) N: \+ ~- ~/ d
2) 247 = 3b - a
4 ?, u {& _1 f3 V f
3) 152 = 3a - 8b
) X: w" W x! M* _* B& X
4) 95 = 11b - 4a
! Q: U7 l+ i/ V n- T" Y
5) 57 = 7a - 19b
/ J5 r& G% L' L, h: _
6) 38 = 30b - 11a
* v2 s* ]7 U* D. `- m
7) 19 = 18a - 49b
* ]5 b0 f4 Z$ o% f
4 V9 D+ q! }6 A0 w* g
所以，(u,v) 为 （18，49）。
- z2 R9 f5 R8 f) J: w: \1 M. L/ A
9 k& J) [2 x) b( a, Y
是否我算错了？如果是的话，错在哪里？
/ Y' t( ~% B: W( c: x% H
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5