- 在线时间
- 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)7 p0 ]+ J- n9 x# d
1) x ≡ 0 / c& O/ j# L x7 \8 E
(mod q1)& {. ]0 ], t5 o- ?; [$ e
x ≡ r2! R: b& W* [: P; b0 x# i
(mod q2)0 Q) M% W2 W( y& |% S) \
2) x ≡ 0 * {; p+ F8 H3 M0 `3 Y9 C2 M
(mod q1)
- v( j; |. p& B( k. `! N1 }% ux ≡q2-r2/ j5 S4 ~# }3 `6 J1 P3 A5 l- N. k
(mod q2)
( c' ?) Q; \3 Y$ _( V( [小于q1q2的解必然一个是奇数,一个是偶数。
$ |4 J! M) w- r# ~: m% u- {/ f, w证明:- H9 v+ J8 i& A' G5 S2 U
根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。2 c2 F4 g% Z* v: T
令方程组1)与2)的解分别为:6 i8 w0 I8 B9 B
x1=a1q1=b1q2+ r27 E N- C! `5 e+ l8 G" _$ Z
x2=a2q1=b2q2+ q2-r23 z& N+ P9 e+ Y
则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)8 M3 F- C9 w+ ~5 Y3 y! W9 h
即:(a1+ a2)q1=(b1+b2+ 1)q25 T! l6 D$ ]' J3 Q0 D }' ~
∵
$ N4 R" M. o; dq1 、q2互素,且x1< q1q2,x2< q1q2,
- M) J8 R1 y7 Z, h" R J7 W/ ^∴
2 h8 M1 i. L* Q0 T* ix1+x2< 2q1q2,$ _. h+ \8 L$ r* O
∴
9 @/ E+ \3 ]9 w) pa1+ a2 =q2 j) a \, g. ^+ m, t/ [, T$ |7 ?
,b1+b2+ 1=q1
& b* R; A# ?4 L( ]. [/ H0 b5 X∵ q2为奇素数,
# r/ T2 a3 Y+ Q2 b8 d∴ a1与 a2既不能同时为奇数也不能同时为偶数。8 i# A# ~7 z* G3 u. V, k
∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。( D) J5 q, {6 O7 }3 b* A. A: w, x
∴ a1与 a2只能一个为奇数,一个为偶数。) A. @, Q% u4 } I2 ~% _2 e: L
∴* }8 |% B, Q, k8 \% Y
x1=a1q1=b1q2+ r2( s3 c) H1 _% s; X# U$ A
x2=a2q1=b2q2+ q2-r2
1 l/ W" x9 P; x% n; i1 b也只能一个为奇数,一个为偶数。* m; f- x" p0 Z8 u( g: b
定理得证。 |
zan
|