- 在线时间
- 0 小时
- 最后登录
- 2009-5-8
- 注册时间
- 2009-2-19
- 听众数
- 5
- 收听数
- 0
- 能力
- 0 分
- 体力
- 14 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 7
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 6
- 主题
- 4
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   2.11% 该用户从未签到
 |
引理1.59 F/ J8 v% m' E
若q1 、q2为奇素数,则以下同余方程组/ u9 } x; v- s4 A+ H# r
1) x ≡r1
, b* ?* i5 H( ~2 f* ?1 t j3 k' K# {% y0 K+ v
(mod q1)
8 u- z3 K/ u9 D S. K8 {! ~( {: yx ≡ r2
; S8 w6 y6 `: Q; [0 Z(mod q2)$ `) E8 i( g# r' J5 F+ d) [8 x
2) x ≡ r1
! n" j3 k& z' {9 G0 Y* l(mod q1)
" e1 w1 \" m" m$ _6 vx ≡q2-r2
% n7 i$ y5 x' |8 P' ^8 ^& C(mod q2)$ Y/ ~0 L: m) c, M( V
3) x ≡q1-r1# w7 H+ S1 ^8 ^" C1 X3 {! ] Z, ~/ ~
* A/ Z. n9 H! K+ d
(mod q1)
6 P# u' m2 w) K0 r: e/ dx ≡ r2 ( _* c+ u- S: ^+ j
(mod q2)4 A/ c! z/ q" _- Z% W2 l E2 k8 @
4) x ≡q1-r1 0 L% m$ j. E9 }9 M( ^% P8 o: q' W' ]
(mod q1)
' i' }9 ^' x2 S% z+ \0 c5 sx ≡q2-r2+ o; u0 i$ _7 m! N' r' a
(mod q2)" n; ]- B6 h9 m
小于q1q2的4个解必然2个为奇数,2个为偶数。
& Z9 d0 i3 _% k2 |证明:$ w: k2 m4 X: M4 d: F4 `$ ^
根据孙子定理,每个方程组都有小于q1q2的唯一解。
* [1 M8 N( V: G5 Y- @) H令同余方程组1)、2)、3)、4)的小于q1q2的解分别为:
; S; t. d2 }* ^+ }+ O8 ux1=a1q1+ r1=b1q2+ r21 E* l: W+ n7 u5 x
x2=a2q1+ r1=b2q2+q2-r2. [' W3 A% ^+ S- h7 ~
x3=a3q1+ q1-r1=b3q2+ r2* z5 [6 `; T, v# Z+ Y) q% M1 u7 J
x4=a4q1+ q1-r1=b4q2+q2-r2% D7 U! ^1 _4 L. I& M
则
! L+ j6 Q! Z. R" y/ n6 H) l" c; y( wx1+x4=(a1+ a4+1)q1=(b1+b4+1)q2
$ [$ @0 S S% N+ d1 s1 q即 F2 l9 j7 n8 K; @" i
a1+ a4+1= q2,b1+b4+1= q1
( v) _/ x& |; G0 o4 V6 f∴9 t/ i5 w1 o; e. y* O4 b
a1与a4 、b1与b4只能同为奇数或偶数。因此可推出,x1若为奇数,x4便为偶数;x1若为偶数,x4便为奇数。即,x1与x4总是一奇一偶。
/ ~# i2 t% D! l同理可证x2与x3也总是一奇一偶相对的。
) p. W6 K) @ O/ Z$ D- ?即是说,x1、x2、x3、x4这4个解中,总是2个为奇数,2个为偶数。
# k9 T: ]9 V4 ~. x: d6 w9 C4 x0 O定理得证。 |
zan
|