- 在线时间
- 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)
* d" ?/ u: k0 [" E9 J1) x ≡ 0 # W4 l1 N2 `/ u; c- a
(mod q1)9 |3 }0 k; g" E1 z3 t1 p7 Z7 w0 V" p
x ≡ r28 Y5 i; V: V6 G) i7 d+ @- ]
(mod q2); w! Y6 [# B4 \' f' n3 T1 ~# l' i
2) x ≡ 0
* f1 z2 T4 u- x$ Y R. \* Z(mod q1)5 a: t5 U6 K. I+ S$ K
x ≡q2-r2
- V5 }$ a" S4 ^' x(mod q2)
8 O9 U+ ^1 A4 R' x小于q1q2的解必然一个是奇数,一个是偶数。
0 d, h' D' I6 X; b( r* _证明:0 y7 G( M* e% |+ \
根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。/ `' u" o/ N5 @ H) K! l
令方程组1)与2)的解分别为:
Z8 k$ h! f$ Y% L1 b; K" E0 f5 Hx1=a1q1=b1q2+ r2; o5 @2 K/ X. v1 \0 b! h+ v
x2=a2q1=b2q2+ q2-r28 f( X" ~. B3 e) C$ b
则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)1 N" q: |5 G* t1 H! Q+ c" ]
即:(a1+ a2)q1=(b1+b2+ 1)q28 Q% ?2 Y& o) t: S3 x. B
∵- z' {6 ~ P n* v& N, S
q1 、q2互素,且x1< q1q2,x2< q1q2,
3 J9 w& z& S; m% l; Q3 `2 R# B∴
) s" ]1 F7 V m" Wx1+x2< 2q1q2,
5 A1 h0 s% L+ @2 w/ _6 r! h∴5 J' ]2 Z- o8 o% I
a1+ a2 =q2+ r! R) L# n- u; a. V0 @, z
,b1+b2+ 1=q18 K0 v" W* ]* k" k% N# h2 t3 B
∵ q2为奇素数,
( e# `' X; a0 l1 L* Z* J∴ a1与 a2既不能同时为奇数也不能同时为偶数。# A8 r1 D& }' s7 V! ]5 s2 P( ~
∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。
( V r) w$ l; Y z6 y5 g6 ?. O∴ a1与 a2只能一个为奇数,一个为偶数。% b+ g3 ~, ?0 u1 @7 q3 r5 j+ Q
∴8 n5 l# T. L+ }9 L5 {( G
x1=a1q1=b1q2+ r2. E {$ S( r$ {8 @( p! s! j
x2=a2q1=b2q2+ q2-r2. q+ e3 U( w0 i
也只能一个为奇数,一个为偶数。
+ {/ k( E8 g c8 c2 Y定理得证。 |
zan
|