- 在线时间
- 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.4 若q1 、q2为奇素数,则以下同余方程组1)与2). z* l8 Z( ~6 r
1) x ≡ 0
/ n* ?1 M; u5 w0 ?3 f(mod q1)
( Q& }/ P- J- h, ax ≡ r29 o" F* ]' s0 j$ v7 K
(mod q2)) j$ u6 p5 A# H; J) v/ `
2) x ≡ 0 & k7 f/ u1 i/ w6 }) C6 w: Q
(mod q1)
% q; m a1 c0 Rx ≡q2-r2
0 a$ ]3 p4 i8 G, x( W( E(mod q2)
( J( p3 [ S8 L3 y小于q1q2的解必然一个是奇数,一个是偶数。
2 P' \+ N( ?+ I2 l. Y9 L' G证明:
, @- b% [, U7 C# E9 y1 I: E根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。& s2 H% O0 i; W5 g, A
令方程组1)与2)的解分别为:- o- R) f, U- x
x1=a1q1=b1q2+ r2
0 ~# M3 _7 W/ d, z) fx2=a2q1=b2q2+ q2-r2
9 V0 f9 a* b: s- z) J# P则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)- v% r& f6 ]' q y: K
即:(a1+ a2)q1=(b1+b2+ 1)q26 S: v' s6 Y% j" Q
∵6 o& I4 L" S* U
q1 、q2互素,且x1< q1q2,x2< q1q2,
8 v+ [" h, n& ?$ M/ v7 C& J∴
: B. y, G5 R6 u, s6 {1 T* \$ ~2 _x1+x2< 2q1q2,4 f+ e' l$ {; t3 N1 ^4 c8 i
∴
1 b: ^/ c$ X; W) _% ia1+ a2 =q2
3 ^" v% r _# i: P8 b,b1+b2+ 1=q18 y. C5 ]6 A% F
∵ q2为奇素数,/ P2 w$ c' r1 f& l6 Z
∴ a1与 a2既不能同时为奇数也不能同时为偶数。7 t: k) K: @7 [
∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。; Y7 O% i* c3 x% \3 T
∴ a1与 a2只能一个为奇数,一个为偶数。) M4 _! t+ h q1 A7 F8 E
∴
: O( I- |7 v- }: `" H$ cx1=a1q1=b1q2+ r2* y1 h. J8 Z$ y- f" B# j$ R5 X
x2=a2q1=b2q2+ q2-r2
1 O: B( t# n- ?也只能一个为奇数,一个为偶数。
& S( l! b5 o# |定理得证。 |
zan
|