連立合同式の商の定理について

質問

連立合同式の商の定理について教えてください。
x,yを整数　m,aを自然数とするとき

ax≡ay (mod m) ⇔ x≡y ( mod m/GCD(m,a) )

(おかしな表記ですみません。( mod -)は分数式です)

が「商の定理」と習いましたが、これは連立合同式

x≡a (mod K)
x≡b (mod L)
x≡c (mod M)

のK L M が「互いに素」ではないときに適用できる定理だと思うのですが、うまく理解できません。

解らない点:(1)
連立合同式
x≡a (mod K)
x≡b (mod L)
の時、K L のGCDが「1」で「互いに素」と覚えていますが
x≡a (mod K)
x≡b (mod L)
x≡c (mod M)
の時も　K L MのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？

解らない点:(2)
x≡a (mod K)
x≡b (mod L)
x≡c (mod M)
で　K L M が「互いに素」ではない場合、商の定理を適用した解法でx≡y ( mod m/GCD(m,a) )を求める方法。

K L M が「互いに素」ではない時、K L Mの最小公倍数を使えばよいのは解るのですが、GCD(m,a)の「a」が理解できません。「m」はK L Mの最小公倍数だと思うのですが、「a」は何になるのでしょう？

x≡2 (mod 4)
x≡4 (mod 12)
x≡3 (mod 9)
の場合を例として、具体的に解法を教えてください。
よろしくお願いします。もしも上式が連立合同式として成立しないのであれば、その理由も教えてください。
中国式余剰定理では、( mod ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。
具体的な解法で、よろしくお願いします。

回答No.2

shkwta · ベストアンサー

x≡a (mod K)
x≡b (mod L)
x≡c (mod M)

この連立合同式は、
LMp≡1 (mod K)
MKq≡1 (mod L)
KLr≡1 (mod M)
で求められるp, q, rを用いて

x = aLMp + bMKq + cKLr

とすればよいのですが、この計算をするためには、KとLが互いに素、LとMが互いに素、MとKが互いに袖なければなりません。
したがって、GCD(K,L,M)=1 では不十分です。３つ以上の「互いに素」はどの２つをとっても互いに素という意味です。
------------------------
K,L,Mが互いに素でない場合の例として
x≡13 (mod 60)
x≡43 (mod 90)
x≡13 (mod 150)
を解いてみます。

まず、中国剰余定理により、PとQが素であれば
y≡t (mod PQ) ⇔ y≡t (mod P) and y≡t (mod Q)

これにより、K, L, Mを素因数分解すると
K = 2^2・3・5
L = 2・3^2・5
M = 2・3・5^2
ですから、つぎの９個の合同式が成立します。

x≡13 (mod 60) ⇔ x≡1 (mod 4) and x≡1 (mod 3) and x≡3 (mod 5)
x≡43 (mod 90) ⇔ x≡1 (mod 2) and x≡7 (mod 9) and x≡3 (mod 5)
x≡13 (mod 150) ⇔ x≡1 (mod 2) and x≡1 (mod 3) and x≡13 (mod 25)

ここで、
x≡1 (mod 4) ⇒ x≡1 (mod 2)
x≡7 (mod 9) ⇒ x≡1 (mod 3)
x≡13 (mod 25) ⇒ x≡3 (mod 5)
ですから、上の合同式９個のうち６個は不要です。残りの３個、

x≡1 (mod 4)
x≡7 (mod 9)
x≡13 (mod 25)
はK,L,Mが互いに素の形です。これを解けば、最初の連立合同式の解になります。
-----------------------------------------------------
質問者様の例で、

x≡2 (mod 4)
x≡4 (mod 12)
x≡3 (mod 9)

これは解がありません。上の問題と同様に計算してみましょう。分解できるのは２番目の式だけです。
x≡4 (mod 12) ⇔ x≡0 (mod 4) and x≡1 (mod 3)
ところが、得られた２つの合同式は、x≡2 (mod 4), x≡3 (mod 9)と矛盾します。
したがって、解はありません。

以上のように考えましたが、結局「商の定理」を使う機会がありませんでした。

補足

丁寧な解説、ありがとうございました。
(mod ○)が互いに素ではない時の解説が参考書にあるのですが、よろしければこれの具体的な解法についても教えて頂けると助かるのですが。

X≡3 (mod 12)
X≡19 (mod 8)

という合同式なのですが。

回答No.3

shkwta

o.2の補足への回答です。

ア　X≡3 (mod 12)
イ　X≡19 (mod 8)

イを簡単にして、
ウ　X≡3 (mod 8)

8=2^3 なので、ウは分解できません。
12=2^2・3なので、アは

エ　X≡3 (mod 4)
オ　X≡0 (mod 3)

エはウから出るので、ウとオだけが残り、
ウ　X≡3 (mod 8)
オ　X≡0 (mod 3)

ここで次の合同式を考え、
カ 3p≡1 (mod 8)
この十分条件は
キ p＝3

ウ・カ・キ・オより
x≡3×3×3 (mod 24)
よって、
答　x≡3(mod 24)
--------------------------
参考書はどんな解法ですか？商の定理を使うのでしょうか。

補足

回答ありがとうございます。
私の参考書は「数学」の専門書ではなく、ＲＳＡ系統暗号書籍なので数学的な解説があまり丁寧ではありません。お答え頂いた合同式では、以下のような解説です。

ア　X≡3 (mod 12)
イ　X≡19 (mod 8)
アの方程式から、x=3+12y
イのxを3+12yで置き換えて
12y≡16(mod 8)を得る。
（この辺りから、私には理解困難になります）
gcd(12,8)=4　は16を割り切るから、合同式は解を持たなければならない。
↑
（これを、商の定理と理解したのですが）
12y≡16(mod 8)
は、
12y-8z=16と同値であり
3y-2z=4となる。
したがって、
3y≡4(mod 2) となる。
しかし
3≡1(mod 2) であるから、
y≡0(mod 2) である。
↑
（これで、お答え頂いた解法に戻る気がします）
ある整数kに対して、y=2Kであるから
x=3+12yにおいて、yを2Kで置き換えれば
x=3+24k となる。

以上が書籍の解説です。
頂いた回答を参照して、答えは同じですから理解できました。ありがとうございました。
数学の勉強ではなく、ネットワークセキュリティー関係の必要に迫られて、RSAや中国式余剰定理を勉強しています。
現在格闘中の問題は、例えば
与えられた整数「2 6 11」と「5 3 4」
これを(mod 18) または(mod 9)を法とする関係で、整数解「9 13 6」を得るための数式及び解法です。
（或いは条件に、整数または自然数としての「16」も入るかもしれません。意味は、整数解「9 13 6」を得るための必要条件、または十分条件として「16」も必要であるかもしれないということです）

私はこれを中国式余剰定理を使った合同式として考えたのですが、何かご意見があれば是非参考にさせて頂きたいと思います。

回答No.1

yoikagari

質問1

＞KとLとMのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？

この場合は駄目です。
KとLが互いに素かつKとMが互いに素かつMとLが互いに素でなければなりません。
たとえばK=4、L=6、M=9のときKとLとMのGCDは1ですが、4と6は互いに素ではありませんし、6と9も互いに素ではありませんので、K=4、L=6、M=9のときKとLとMは「互いに素」ではありません。