- 在线时间
- 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)
) _9 J$ q5 E4 p1) x ≡ 0 3 v. C, ]( J) a2 V/ C4 G
(mod q1)
$ r U' W* G2 t% R0 ?, L: C5 fx ≡ r2
0 t0 E! G1 W9 V- c A# W( A8 W(mod q2)* u/ W/ _4 _; |( c2 T! r
2) x ≡ 0 0 F) t: K9 E( \
(mod q1)
6 \" w4 K; [/ V$ \7 s1 y! K& ^x ≡q2-r25 z% f* u- P9 D8 U
(mod q2)+ G% h# D- \! a) a3 W8 n0 f5 l7 q
小于q1q2的解必然一个是奇数,一个是偶数。
3 V+ e2 l, X$ e证明:! v5 s* w# E5 ~- T
根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。
6 [, _1 e$ q. v. I% `令方程组1)与2)的解分别为:
6 h' c" _ i& h. N; R. wx1=a1q1=b1q2+ r2' q2 j. w6 y: b) r
x2=a2q1=b2q2+ q2-r2
* \+ D' ~0 K. X3 y- F则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)8 \* h9 D/ J8 @: o
即:(a1+ a2)q1=(b1+b2+ 1)q26 Q% P3 ]" p5 E3 ^
∵( A* R8 _0 u! W" ~
q1 、q2互素,且x1< q1q2,x2< q1q2,
8 g: A4 ?/ N! e( S2 h% E∴# x2 @8 y$ P8 V5 k, z$ J
x1+x2< 2q1q2,( }2 d6 ~* L' L4 e( T" p+ D2 H
∴
9 n1 ^# O4 p$ Da1+ a2 =q26 x6 {/ B$ E8 G; f8 }; h# L( X
,b1+b2+ 1=q1
* b+ W6 _/ F, A. Q+ w5 `+ M' f$ b: d∵ q2为奇素数,. v; T( }+ a0 u) u/ c4 p
∴ a1与 a2既不能同时为奇数也不能同时为偶数。
5 }% J6 u& m, n; ^9 J( m( L7 y0 ^∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。% I; C. Q/ R- K3 Y
∴ a1与 a2只能一个为奇数,一个为偶数。
! l% Q9 J1 {# C; R; t' `∴
, @9 [$ \( V5 o" Yx1=a1q1=b1q2+ r2
, w0 [1 X& t) u6 ?5 Rx2=a2q1=b2q2+ q2-r2
. |* J9 _2 d6 e7 S% ~也只能一个为奇数,一个为偶数。
4 u' v6 s6 Q& O9 N& C" U定理得证。 |
zan
|