- 在线时间
- 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)+ f D( B" B1 D2 z% ^
1) x ≡ 0
( u n ]6 W% y v; K(mod q1)
: h6 {$ S+ P, L8 Sx ≡ r2# N5 `& H% O& A& [! \1 Z
(mod q2)
( _: {2 P n3 K7 M; Z2) x ≡ 0
. L3 l, {+ S V& r6 u(mod q1)7 f' D- a, c: h. S8 W5 K
x ≡q2-r2
9 C4 [$ @% j$ r3 w- V) d(mod q2)
6 d+ u/ T- x% c+ f小于q1q2的解必然一个是奇数,一个是偶数。
# B) B6 V8 z. X4 g7 h' w( m! P1 H证明:+ A, B3 z) ^" h- J) x/ H
根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。0 B1 c" t e: ^9 x8 i. `
令方程组1)与2)的解分别为:
& @- r! a3 s3 |' P, Ux1=a1q1=b1q2+ r2
9 @3 T2 h& \6 T0 sx2=a2q1=b2q2+ q2-r2
% `" J. A9 m L$ O8 W则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)& j' ~( N" |8 I' m4 v. Q
即:(a1+ a2)q1=(b1+b2+ 1)q25 R& A9 T1 m2 ^3 {
∵
. g1 w8 [ @+ F3 C( t& M' Fq1 、q2互素,且x1< q1q2,x2< q1q2,: o3 t5 |% _: ]" M+ m
∴
& E( V* X) _- T9 Gx1+x2< 2q1q2,
# e- n/ _0 W* z∴+ L% d7 b8 J4 d2 X0 u2 s8 k
a1+ a2 =q24 V* Y$ c% O H/ l1 H* [4 \
,b1+b2+ 1=q1" J) x2 O+ O7 K6 ?6 B! O
∵ q2为奇素数,
7 E! [5 u0 h! n) i# e, y8 r∴ a1与 a2既不能同时为奇数也不能同时为偶数。% d& V. J4 v( n
∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。
0 I4 h# X+ |8 q! j" l; V∴ a1与 a2只能一个为奇数,一个为偶数。* c" q$ \7 Y& c. k* d& v' E) t$ O
∴7 } ^" p( u5 m3 ], K, R0 i+ k
x1=a1q1=b1q2+ r2
) z0 I9 }, H& H: J8 wx2=a2q1=b2q2+ q2-r2- k" p" }/ i( p. w- }, C/ @
也只能一个为奇数,一个为偶数。 W; S2 [- r4 h
定理得证。 |
zan
|