- 在线时间
- 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)* b2 ?6 f% l! v
1) x ≡ 0 / E, b" `7 R# C! t3 W/ b. h
(mod q1) h4 m: X8 o3 [7 p
x ≡ r2$ `# a0 s$ p1 u/ e
(mod q2)( c" B, q' e% t: G: h
2) x ≡ 0
! L" ], V- }% q4 d. v' d. h- ` s+ [(mod q1)' H: H* Y$ P$ R
x ≡q2-r2/ l7 z. X( \- v' @
(mod q2)
" b# p- I d0 R! [小于q1q2的解必然一个是奇数,一个是偶数。
& N5 L1 D' s, Z# Z- H7 p证明:: U# A- l( \# n% G& L/ w
根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。 d2 S! z4 z, D- V$ T1 ?4 D
令方程组1)与2)的解分别为:
9 `: ~, l- h& a3 b- Q' V- \, ~x1=a1q1=b1q2+ r2) Q. g. i: ?+ k: A& k) x
x2=a2q1=b2q2+ q2-r2
; @4 \$ P( H8 D7 N4 C则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)
5 c/ Q( o$ t1 G1 M3 h, {. s即:(a1+ a2)q1=(b1+b2+ 1)q2* i+ H- c* R' o* D1 f# h
∵
: G; l! V0 D* I0 o' K {; F/ rq1 、q2互素,且x1< q1q2,x2< q1q2,3 D7 t& L9 d6 B
∴) _3 m; S1 O) V
x1+x2< 2q1q2,
# f# `1 X) V9 F∴
- p. _) p. e% P) ta1+ a2 =q2
% e* `) a/ T1 P },b1+b2+ 1=q1
3 ?8 s$ d2 y1 \, s2 O$ A∵ q2为奇素数,
1 }* w0 K, J- F: b5 l# {∴ a1与 a2既不能同时为奇数也不能同时为偶数。 ^$ \* Y4 M. s! a+ u
∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。" [8 G$ Z c% |' Y2 }
∴ a1与 a2只能一个为奇数,一个为偶数。6 u; A% k5 l9 n
∴$ z" Z/ a. r. f. q0 |5 R. }
x1=a1q1=b1q2+ r2( y z/ l; |$ x% o3 g
x2=a2q1=b2q2+ q2-r20 o1 N e3 N$ f% ~! S4 p4 P( J4 d& v
也只能一个为奇数,一个为偶数。8 ?, P# E/ n1 E$ `) u5 r
定理得证。 |
zan
|