中国剰余定理 3数

質問

余りが条件式を満たすがわからないので質問します。
p,q,rどの2つをとっても、互いに素な自然数とする。a,b,cを任意の整数とする。このとき、　x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たす整数ｘが、0からpqr-1までの間に1つ存在する。この定理の証明は、
(qr)s≡1 mod(p),(rp)t≡1 mod(q),(pq)u≡1 mod(r),を満たすs,t,uを求めることから始まります。sであれば、(qr)s+py=1・・・(1)という１次不定方程式を解くことで、得られます。q,rがpと互いに素であるから、qr,pが互いに素なので(1)を満たすs,yは存在します。同様にt,uが得られます。x=a(qr)s+b(rp)t+c(pq)u・・・(2)とおけば、xは条件式を満たします。(2)をｐで割った余りは、a*1+0+0=aとなります。qで割れば余りb,rで割れば余りc,となります。ここからがわからない箇所です。このxをpqrで割った余りも条件式をみたします。
まず、自分の計算では、x=a(qr)s+b(rp)t+c(pq)u=pqr{as(1/p)+bt(1/q)+cu(1/r)}となり余りが出ません。そして条件式x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。

回答No.1

f272 · ベストアンサー

あなたは何も言っていないに等しいから、別に間違いがあるわけじゃないよね。単に考えを進めていないだけです。
(2)式で出したxがx≡a mod(p),x≡b mod(q),x≡c mod(r) を満たすことはわかったのですね。このxが0からpqr-1までの間にあるかどうかは、いまのところわかりません。
しかし、もしその範囲になければpqrの整数倍を足すか引くかをすることで範囲内に収めることができます(これが「このxをpqrで割った余り」に相当します)。そのうえ、その場合にはpqrの整数倍しか違いませんから、pで割った余りはaのままですし、qで割った余りも...以下省略。

お礼

このxが0からpqr-1までの間にあるかどうかは、いまのところわかりません。
の指摘には、はっとしました。ご指導ありがとうございます。