- ベストアンサー
中国剰余定理について。
以下の画像は、中国剰余定理の互いに素でない場合の説明なのですが、よく分かりません。 なぜこれが、必要十分条件なのかから分かりません。ご教授願いたいです。すみません。
- みんなの回答 （25）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (24)
- f272
- ベストアンサー率46% (8052/17217)
- f272
- ベストアンサー率46% (8052/17217)
#21に書かれている文章はどこから持ってきたのですか？文脈を離れて理解しようとしても困難です。それ以前にそれぞれの文字が何を意味しているのかが書かれていたはずですよね。そういう大事な情報を欠落させたまま提示されても困ります。すべてを書く気がないのであれば，必ず元情報がどこにあるのかを書いてください。
補足
こちらのURLのことです。ご教授願いたいです。すみません。 https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14234555989
- f272
- ベストアンサー率46% (8052/17217)
書いてある通りだろう。 何が理解できないんだ？
補足
なぜ、dの倍数と言えるのかです。あなたは、dの倍数になるとは、言っていないですよね。 ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
最初からずっとそのように言い続けているよね。小学生でもわかる話です。日本語が不自由であるのなら最初からそのように言って欲しい。
補足
解xが存在すると仮定すると x=b1+m1k1=b2+m2k2 なる整数k1, k2が存在する。 これより b1-b2=m1(-k1)+m2k2 はdの倍数である。 逆に、b1-b2がdの倍数であると仮定すると b1-b2=m1(-k1)+m2k2 なる整数k1, k2が存在する。 x=b1+m1k1=b2+m2k2 とおけば、これは解になっている。 これは、どう言う意味でしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
同じことを別の言い方をすれば， iaとjaとは，a，2a，3a，...，(b-1)aのうちの2つで，bで割った余りが同じになるものです。
補足
つまり、ia とja をbで割った余りが同じという事でしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
「まずa，2a，3a，...，(b-1)aを考えます。これらをbで割った余りが同じものがあればそれをiaとja(ただしi<j)として」と言いました。これが理解できないのですか？ あなたの言う「割る数」って何ですか？ 何も考えずに人に聞くのではなく，自分で真面目に考えてください。
補足
そうです。ia とjaは一体何なのでしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
> さっきのa,2a に、例えば、a＝3とすると、3と6でわった余りが同じということでしょうか？ 違います。 「まずa，2a，3a，...，(b-1)aを考えます。これらをbで割った余りが...」と言っているように，3と6で割るのではなく3と6を割るのです。 > なぜ、余りをia とjaにしたのでしょうか？ そんなことはしていません。 > これが同じになるときとは例えば、どういうときでしょうか？ > ia とjaがなぜ浮かんできたのでしょうか？ こたえる意味がありません。真面目に回答を読んでください。
補足
では、ia とjaは、割る数の事を言っているのでしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
要するに「まずa，2a，3a，...，(b-1)aを考えます。これらをbで割った余りが同じものがあればそれをiaとja(ただしi<j)として」の意味が全く分からないと言っているのに等しいわけです。 これまでいくつも質問をしてきたのに，今更「ia とja をbで割るということでしょうか？それの余りが等しいということでしょうか？」なんてことを言うのはなぜですか？日本語が理解できないのであれば，こんな問題を考える以前の話です。たぶん中国剰余定理が何を言っているかも分かっていないのでしょう。こんな状況では何を質問しても無駄です。
補足
さっきのa,2a に、例えば、a＝3とすると、3と6でわった余りが同じということでしょうか？ご教授願いたいです。すみません。なぜ、余りをia とjaにしたのでしょうか？これが同じになるときとは例えば、どういうときでしょうか？ia とjaがなぜ浮かんできたのでしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
aと言われて，aの倍数のことだと受け取る人はいません。わけのわからないことを言わないように。
補足
では、ia とja をbで割るということでしょうか？それの余りが等しいということでしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
> i やjが違うとすると、ia のa とjaのa は同じなのですよね。 同じ文字を使っているのだから同じに決まってます。もし違うものなら何も相手に伝えることができません。 > a と2a が余りが同じになるという事でしょうか？ 例えばそういうことです。最初から何度も何度もそう言っています。
補足
このa は、a の倍数のことでしょうか？ご教授願いたいです。すみません。
関連するQ&A
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 中国式剰余定理の教え方
中国式剰余定理の証明で、ガウスの証明以外の証明がありますか？ 中学３年生に説明しようとして、詰まってしまいました。 素因数分解、最大公約数、最大公倍数、剰余系ぐらいを知っている程度です。 ずらずら書き出して、規則性を見つけさせて、一般的な求め方が分かるというようにしたいののですが、やっぱり無理ですかね、いきなりは？
- ベストアンサー
- 数学・算数
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- 剰余の定理にて
お世話になります。 次の剰余の定理の問題のとき方のヒントを教えていただけないでしょうか？ ---------------------------------------------------------------- P(x)を(x-1)で割った場合余りは[1]、(x-2)(x-3)で割った場合は余りは[5]。 ではP(x)を(x-1)(x-2)(x-3)で割った場合の余りはいくつか？ ---------------------------------------------------------------- 通常(x-1)のような一次式で割る場合はP(1)＝a+b+c=1、 というように行って連立方程式でa,b,c,のそれぞれの値を求めているのですが、 (x-2)(x-3)のような2次式の場合、どのように扱って解を導き出したらいいのかがわかりません。 よろしければその部分をどのように解いたらいいのか、またどうしてそのようになったのか説明を加えていただけないでしょうか。 ご教授お願いいたします。
- ベストアンサー
- 数学・算数
- 中国剰余定理 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) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 剰余の定理について教えてください
剰余の定理1 P(ｘ)を ｘ－αで割った時のあまりは P(α) 剰余の定理2 P(ｘ)を 1次式aｘ+ｂで割った時のあまりは P(-b/a)-a分のbのつもり これは理解しています。 ところで 整式P(ｘ)を ｘ+２で割った時の余りが-1、２ｘ-１で割った時の余りが4である時、P(ｘ)を (ｘ＋２）(２ｘ－1)で割った時の余りを求めよ。という問題をとく時、つまり２次式で割るという時 余りを aｘ＋ｂとするのはなぜですか? P(x)=(x+2)(2x-1)Q(x)+ax+b どうして、余りを(ａｘ＋ｂ)にするのですか？ 教えてください。
- ベストアンサー
- 数学・算数
補足
念のため確認ですが、ia とjaをbで割った余りが等しいと仮定する。と言う事をあなたは、言いたかったのですね。合っていますでしょうか？ご教授願いたいです。すみません。念のためです。