作业帮这个简单的问题怎么用中国剩余定理来证明?我在一本书上看到这样一段话（我改了一下）其实不用中国剩余定理,我也能知道怎么去解,但是他说由中国剩余定理知,我就不知怎样知了
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/16 22:35:03
这个简单的问题怎么用中国剩余定理来证明?我在一本书上看到这样一段话（我改了一下）其实不用中国剩余定理,我也能知道怎么去解,但是他说由中国剩余定理知,我就不知怎样知了
这个简单的问题怎么用中国剩余定理来证明?
我在一本书上看到这样一段话（我改了一下）
其实不用中国剩余定理,我也能知道怎么去解,但是他说由中国剩余定理知,我就不知怎样知了
这个简单的问题怎么用中国剩余定理来证明?我在一本书上看到这样一段话（我改了一下）其实不用中国剩余定理,我也能知道怎么去解,但是他说由中国剩余定理知,我就不知怎样知了
题：
相异素数p,q;
C==m mod p;
C==m mod q;
求证以上同余式有且有唯一解,为：C== m mod pq.
解一：
易见C== m mod pq是原同余式的解.
因为gcd(p,q)=1,故原同余式有唯一解.
综上得证.
如要证唯一性,由反证法或同一法立即得证：
原同余式有另一解为C=m+a + pqk,即C==m+a mod pq；代入立即得到a=0 mod pq.故解唯一.
解二：用中国剩余定理,如下.
因为gcd(p,q)=1,故存在s,t使得ps+qt=1.
故
ps==ps+qt mod q==1 mod q,ps==0 mod p
qt==ps+qt mod p==1 mod p,qt==0 mod q
据中国剩余定理,
原同余式的解为 C==mps + mqt mod pq,即c==m(ps+qt)=m mod pq.
得证.
这里利用了中国剩余定理：
当gcd(p,q)=1时,同余式
X==r1 mod p
x==r2 mod q
过程即是中国剩余定理的程序.
若有a==1 modp 且 a==0 mod q
以及b==0 modp 且 b==0 mod q
则X==r1*a+r2*b mod pq.
解三：中国剩余定理的等价变化形式
当gcd(p,q)=1时,同余式
X==r1 mod p
x==r2 mod q
过程即是中国剩余定理的等化变化形式.
若有a==r1 modp 且 a==0 mod q
以及b==0 modp 且 b==r2 mod q
则X==r1+r2 mod pq.
利用这个变式求证本题如下：
gcd(p,q)=1,故存在s,t使得ps+qt=1.从而存在A,B,使得pA+qB=任意整数,这里取pA+qB=m.
易见pA==pA+qB mod q =m mod q; pA==0 mod p;
并且qB==pA+qB mod p =m mod p; qB==0 mod q;
由中国剩余定理的等价变化形式得到原同余式的解
C== pA+qB mod pq,即C== m mod pq.
中国剩余定理可以表述为:
若gcd(m,n) = 1, 则同余方程组x ≡ a (mod m), x ≡ b (mod n)在mod mn意义下的解存在唯一.
于是这里可以这样解释.
显然C都是M是同余方程组x ≡ M (mod p), x ≡ M (mod q)的解.
由解的唯一性, 即有C ≡ M (mod pq).
个人认为这样写确实有点绕弯子, 但是...
全部展开
中国剩余定理可以表述为:
若gcd(m,n) = 1, 则同余方程组x ≡ a (mod m), x ≡ b (mod n)在mod mn意义下的解存在唯一.
于是这里可以这样解释.
显然C都是M是同余方程组x ≡ M (mod p), x ≡ M (mod q)的解.
由解的唯一性, 即有C ≡ M (mod pq).
个人认为这样写确实有点绕弯子, 但是好处是不用将同余式转化为整除条件, 语言上相对统一.
收起