- 在线时间
- 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.5% U, u, `" g z$ [) f
若q1 、q2为奇素数,则以下同余方程组
* }6 Y5 I( q2 g% ?1) x ≡r15 z/ N/ w( H) [ S
. J3 ~8 o2 K7 ?
(mod q1)
0 N+ _( L y! r. i; Tx ≡ r2
- { R" H i3 l3 J; F(mod q2)
: F1 T$ o' Q! G! g# l2) x ≡ r1
: v" C! \1 I7 X1 t(mod q1)% ~: A& f3 `4 l& z9 X6 q+ {
x ≡q2-r2
0 B Q4 e5 {+ y$ I! @5 c(mod q2)
% ~$ k5 G/ M( a. C" r1 I5 w3) x ≡q1-r1; `4 W- c( x+ i- G5 z' b$ L3 [) Y
3 B { o9 {2 @+ \$ J f8 _(mod q1)
9 Z' _/ t& M" g- [x ≡ r2
* I* D: H: S: Q7 ]8 L(mod q2)
0 ]& W8 f: q; L p- g4) x ≡q1-r1
, ?9 @0 J! |, }5 c* ^& i(mod q1)
) {7 a2 Q& a) I, x: w. R5 P1 |x ≡q2-r29 o- Y( h" L+ x- U) s
(mod q2)
- {: M) @$ |$ \1 L/ l9 }7 H# d小于q1q2的4个解必然2个为奇数,2个为偶数。! _# F( i5 v" B C: t
证明:: A/ A# Z% [; g4 {- l
根据孙子定理,每个方程组都有小于q1q2的唯一解。
5 U( Y3 j0 N6 `令同余方程组1)、2)、3)、4)的小于q1q2的解分别为:
5 `* v, \* C! [( I% ox1=a1q1+ r1=b1q2+ r2+ }* ~. b0 b: C% A6 U
x2=a2q1+ r1=b2q2+q2-r2
' X3 X2 P; z. R& Zx3=a3q1+ q1-r1=b3q2+ r2
' ^+ x4 ]2 X/ Y. g5 Yx4=a4q1+ q1-r1=b4q2+q2-r21 [$ L4 S$ p4 k7 [6 G
则
2 u! d N- w, zx1+x4=(a1+ a4+1)q1=(b1+b4+1)q2. w; Z7 a4 ^0 Q( ]* `+ W
即
# U. c' z0 Z6 o3 Xa1+ a4+1= q2,b1+b4+1= q1$ }# |& T6 Q& g% [" |
∴
6 G9 y8 f$ G+ P2 Va1与a4 、b1与b4只能同为奇数或偶数。因此可推出,x1若为奇数,x4便为偶数;x1若为偶数,x4便为奇数。即,x1与x4总是一奇一偶。0 m2 K o' i# \+ Y
同理可证x2与x3也总是一奇一偶相对的。& E p0 i' v* T* b: }, _
即是说,x1、x2、x3、x4这4个解中,总是2个为奇数,2个为偶数。- s% o! O9 t7 F+ Q$ N. i5 y% ?
定理得证。 |
zan
|