- 在线时间
- 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)0 g0 G2 f. v: S/ R5 g7 ^% I3 m
1) x ≡ 0 $ h7 V) j, g+ F9 v2 P( }" c4 @
(mod q1)
8 q/ M; [* I3 i5 H. vx ≡ r2
+ I/ E9 G8 ] z3 D$ o) U) z+ d(mod q2)
8 R0 A! u! B$ q2) x ≡ 0
3 t. R8 y* C$ q(mod q1)
. F+ _" M* ~- e2 g$ bx ≡q2-r2
% v) w4 B& L8 F' D3 v" T(mod q2); [! a- ]7 y( B
小于q1q2的解必然一个是奇数,一个是偶数。
* r: x. ^# x* H. u) M# Z证明:
6 Q/ [. U; m" l! `根据孙子定理,方程组1)与2)都有小于q1q2的唯一解。
" R! ~7 K& F* P+ b& W令方程组1)与2)的解分别为:
4 T U: Z; Z! @0 t& C0 s$ J8 @* px1=a1q1=b1q2+ r2) U' t8 [( ~6 l7 X' u" |) |
x2=a2q1=b2q2+ q2-r24 q) u9 D3 A& p3 |
则:x1+x2= a1q1+ a2q1=(b1q2+ r2)+(b2q2+ q2-r2)
* ^3 o7 m3 V4 [ `% R) A即:(a1+ a2)q1=(b1+b2+ 1)q2
a/ Q+ [& [& G6 \4 k) U7 ]5 V∵: A; _0 G$ e+ N2 Z
q1 、q2互素,且x1< q1q2,x2< q1q2," N# l. S' W: M1 Z; q
∴
9 p8 h: v$ u: e; ^/ ]" n# e4 }4 D- Hx1+x2< 2q1q2,
4 ^& [' n) j5 G5 ]! ?( H, D7 ~∴
( p, @9 w* d, j1 i, T5 B! a- Za1+ a2 =q2# E* d/ x0 q4 a( ?; y' b
,b1+b2+ 1=q1
% t2 F: g: U: i. {5 [∵ q2为奇素数,
+ z* O) i' l8 J; {% U' D∴ a1与 a2既不能同时为奇数也不能同时为偶数。
' h* D# R. C, s" E7 [6 k0 f∵ 若a1与 a2同为奇数或偶数,则有a1+ a2=2b= q2,此与q2为奇素数相悖。+ }* v/ H" ]& [% v( j
∴ a1与 a2只能一个为奇数,一个为偶数。1 I7 a. O2 O6 ^5 e7 [2 B# s! N
∴
# ^% j3 v. o1 ix1=a1q1=b1q2+ r2
& i5 \% F6 P2 e2 w( K/ Z& Xx2=a2q1=b2q2+ q2-r2( N- E" N( v! i B* y
也只能一个为奇数,一个为偶数。( z5 m. _8 T0 T2 |) Z0 |
定理得证。 |
zan
|