- ベストアンサー
中国剰余定理について。
以下の画像についての証明をご教授願いたいです。すみません。n1とn2は互いに素ではありません。
- みんなの回答 （21）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (20)
- f272
- ベストアンサー率46% (8052/17217)
- f272
- ベストアンサー率46% (8052/17217)
> 1以上30以下というのは、具体的に数字を当てはめた例です。 ずっと「まずa，2a，3a，...，(b-1)aを考えます」ということを前提にしていることを言った上でaとbは何を想定しているのかを聞きました。そうするとあなたは「a ＝3と、b＝7の場合です。」と言いつつも1以上30以下なんてことを言う。具体的にどんな数字を当てはめたら1以上30以下というのが出てくるんだ？ > 最初の疑問で、bで割った余りが、なぜ、ia とja になるのか？と言っています。 それ以前の話をスルーしないように。それから上記のようなことはない，とはっきり言ったよね。
補足
以下のURLを見ていただけないでしょうか？ご教授願いたいです。すみません。 https://oshiete.goo.ne.jp/qa/12043864.html
- f272
- ベストアンサー率46% (8052/17217)
全然話がかみ合っていません。 なぜ「1以上の整数で30以下の整数」こんなことを言い出したのか？
補足
最初の疑問で、bで割った余りが、なぜ、ia とja になるのか？と言っています。 これについての説明です。で、 1以上30以下というのは、具体的に数字を当てはめた例です。ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
わたし「まずa，2a，3a，...，(b-1)aを考えます」 あなた「1以上の整数で30以下の整数」 あなた「a ＝3と、b＝7の場合です。」 全然話がかみ合っていません。
補足
bで割った余りが、ia やja になるのか？ 数学的な理解の前に、文章の理解だと思います。 つまり、 条件 (1) 「aとb が互いに素」であるならば， (2) bで割った余りが同じものがあれば (3) iaとja(ただしi<j)として，0<j-i<bかつ(j-i)aはbの倍数 (4) 但し(3)は、aとb が互いに素であることと矛盾 (5) a，2a，3a，...，(b-1)aをbで割った余りはすべて異なる (6) bで割った余りが1であるものが存在 これは、何かを具体的に考えましょう。 例えば 1以上の整数で30以下の整数の内 まず、互いに素の数 例えばa=3 b=7 a 3 6 9 12 15 18 21 24 27 30 bで割ると 9は余り2 12は余り5 15は余り1 18は余り4 21は余り0 24 3 27 6 この条件に合うのは、a=3 b=7 5a＝（１５）の時 ｂで割ると余り１ 上記、ｂで割る数は、全て、a の倍数 と言うことです。ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
何度も「まずa，2a，3a，...，(b-1)aを考えます」と言いましたよね。 aとbがいくつの場合を想定しているのですか？ 真面目に考えてください。
補足
a ＝3と、b＝7の場合です。 この質問にも答えていただけないでしょうか？ご教授願いたいです。すみません。 まず、ここにb-1個の整数 a,2a,3a,...,(b-1)a があるわけです。この中にbで割った余りが同じになる数があるとし、その数はそれぞれia,ja(i<j)と表せると仮定します。つまり、 a,2a,3a,...,ia,...,ja,....,(b-1)a となっているということです。つまり、iとjはどちらもaの係数としてある1,2,3,...の延長線上にある数であり、それは即ち0より大きく、bより小さな自然数であるということです。 これは、合っていますでしょうか？
- f272
- ベストアンサー率46% (8052/17217)
> bで割った余りが、ia やja になるのか？ そんなことはどこにも書いていません。 「数学的な理解の前に、文章の理解だと思います」というのは正しくて，あなたが何も理解していないだけです。 > 例えば 1以上の整数で30以下の整数の内 > まず、互いに素の数 例えばa=3 b=7 どこから「1以上の整数で30以下の整数」が出てきたのですか？「まずa，2a，3a，...，(b-1)aを考えます」と言ったはずです。 これ以下は考える価値なし。
補足
1以上30以下はあくまでも例です。すみません。ご教授願いたいです。
- f272
- ベストアンサー率46% (8052/17217)
https://okwave.jp/qa/q9823391.html でも同じようなことを聞いているが，どういうつもりですか？意味のないことはやめた方が良い。
補足
bで割った余りが、ia やja になるのか？ 数学的な理解の前に、文章の理解だと思います。 つまり、 条件 (1) 「aとb が互いに素」であるならば， (2) bで割った余りが同じものがあれば (3) iaとja(ただしi<j)として，0<j-i<bかつ(j-i)aはbの倍数 (4) 但し(3)は、aとb が互いに素であることと矛盾 (5) a，2a，3a，...，(b-1)aをbで割った余りはすべて異なる (6) bで割った余りが1であるものが存在 これは、何かを具体的に考えましょう。 例えば 1以上の整数で30以下の整数の内 まず、互いに素の数 例えばa=3 b=7 a 3 6 9 12 15 18 21 24 27 30 bで割ると 9は余り2 12は余り5 15は余り1 18は余り4 21は余り0 24 3 27 6 この条件に合うのは、a=3 b=7 5a＝（１５）の時 ｂで割ると余り１ 上記、ｂで割る数は、全て、a の倍数 ∵ j や i は a がついているから ＃１の(4)のｍｎと同じ。 これは、あなたのものを具体例で表したものです。ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
書いてあることをちゃんと読んでいないのですか？ 「これらをbで割った余りが同じものがあればそれをiaとja(ただしi<j)として」というときにi=jの場合を考えてどうするのですか？iとjが同じであればbで割った余りが同じなのだから考える価値がありません。i<jの場合だけが検討する価値があるのです。
補足
ia とja の余りを同じと考えるということは、余りが、もし、a と2a でも同じと考えるということですね？あくまでも例ですが。ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
あなたが言及した https://mathtrain.jp/remainder にx'のことが書いてありますよ。それすら読んでいないのですか？ x′=n1X+a1=a2－n2Y です。
補足
逆に「aとb が互いに素」であるならば，まずa，2a，3a，...，(b-1)aを考えます。これらをbで割った余りが同じものがあればそれをiaとja(ただしi<j)として，0<j-i<bかつ(j-i)aはbの倍数になります。これはaとb が互いに素であることと矛盾しますから，a，2a，3a，...，(b-1)aをbで割った余りはすべて異なることが分かります。そうすると必ずこれらの中にbで割った余りが1であるものが存在します。それをkaとすればka=lb+1です。つまりax+by=1は整数解(x=k,y=-l)を持つことが分かります。 で、質問なのですが、(ただしi ＜j)ではなく、なぜ、（ただしi≦j)にしなかったのでしょうか？ご教授願いたいです。すみません。
- f272
- ベストアンサー率46% (8052/17217)
だから既に書いたように a1≡a2(mod gcd(n1,n2)) であれば x≡a1(mod n1)かつx≡a2(mod n2)を同時に満足するxが0≦x<lcm(n1,n2)の範囲にただ一つだけ存在する と何度も何度も言っています。 例えば，x≡1 (mod 3)，x≡4 (mod 9)であればx=4がある。 書いてあることの意味すら分からないようなら，まずそれぞれの用語の意味を調べてください。
補足
すみません。あなたのコメント x'は連立合同式を満たすのですから，x'をlcm(n1,n2)で割った余りであるxも連立合同式を満たします。またlcm(n1,n2)で割った余りなのだから，xが0以上 lcm(n1,n2)であることとも当然です。 のx｀とはなんでしょうか？ご教授願いたいです。すみません。
- 1
- 2
関連するQ&A
- 中国剰余定理について。
以下の画像は、中国剰余定理の互いに素でない場合の説明なのですが、よく分かりません。 なぜこれが、必要十分条件なのかから分かりません。ご教授願いたいです。すみません。
- ベストアンサー
- 数学・算数
- 中国剰余定理 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) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。
- ベストアンサー
- 数学・算数
- フェルマーの大定理 n=3の場合の証明
フェルマーの大定理・n = 3の場合の証明について質問です。 オイラーはx^3 + y^3 = z^3をx = a + b、y = a - bとおき、整理することによって、 z^3 = 2a(a^2 + 3b^2) と変形し、n = 3の場合のフェルマーの大定理を証明しました。 そこで、質問です。 【2a】と【a^2 + 3b^2】が、互いに素な場合は無限降下法をつかって証明できるようですが、 【2a】と【a^2 + 3b^2】が、互いに素ではなく、1以外の公約数を持つ場合、どのようにして証明すればよいのでしょうか？ 皆様のご教授をお待ちしております。
- 締切済み
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 高校数学。中国剰余定理。
おはようございます。早速質問させて頂きます。 5で割ると3余り、7で割ると6余る整数で、2009以下の整数全体で最大のものは何か。 解説 7で割ると6余る整数....(1) 6,13だから、これと 5で割ると3余る整数....(2) をともに満たすものとして13がある。 ☆nを、(1)(2)をともに満たす整数とすると、n-13は7でも5でも割り切れるから7,5の最小公倍数である35の倍数である。 ここが理解出来ません。 どうしてn-13は7でも5でも割り切れるのですか？ どなたかよろしくお願い致します。
- 締切済み
- 数学・算数
- 互いに素であることの証明問題です
互いに素であることの証明問題です a と b は２つの整数であるとします 今 a と bは互いに素であることが分かっているとして a^n と b が互いに素であることを証明しなさい (nは n＞0 の整数) という問題なのですが 互いに素になることは分かるのですが 証明をせよと言われるとどうしていいか分かりません 数学的帰納法を使えばいいのでしょうか？？ お手数ですがお分かりになられる方 教えていただけませんか お願いします
- ベストアンサー
- 数学・算数
- 証明したいことを証明の途中に使う
nとaが互いに素 ⇔ nとn-aが互いに素 の証明で2つ疑問がわいたので、質問します。 nとaの最大公約数をdとおくと n=Nd a=Ad (NとAは互いに素 これは背理法の証明 がインターネットでしらべれました。) とおけます。このときn-a=(N-A)dです。 ここからが疑問です。NとAが互いに素より、NとN-Aも互いに素です。 自分はこの文は、nをN、aをAと置き換えてはいるが証明したいことであり、成り立つかわからないので証明の途中には使っていけないと思いました。証明の続きは、 よってdはnとn-aの最大公約数にもなるから、nとaが互いに素 ⇔ nとn-aが互いに素です。で終わっていますが、２つ目の疑問が残りました、自分はd=1を証明しないといけない気がします。 自分の考えに間違いがあったら訂正をお願いします。
- ベストアンサー
- 数学・算数
- 既約剰余類群の証明
１つめは剰余類の掛け算。2つめは互除法の原理がわからないので質問します。 読んでいる本では、(a,b)でaとbの最大公約数を表すことにし、(k,n)=1⇔ kとnは互いに素。￣0(本では0の上に￣)を余りが0の類としています。 定義 Z/nZの部分集合 {￣K|(k,n)=1,1≦k≦n-1}は×に対して群になっている。これを(Z/nZ)*と書き、既約剰余類とよぶ。と書かれていて。 ×に関して閉じていることを確認しましょう。nと互いに素であるk,lがあるとき、その積klもnと互いに素になります。klをnで割った商をq,余りをmとすると、 kl=qn+mと書くことができます。kl≡qn+m (mod n) ∴kl≡m (mod n)より、ここからが1つめのわからない計算です。￣ｋ×￣ｌ=￣ｍ 自分は、n=10,k=3,l=9,m=7 3×9=2×10+7として3を２で割った余り、9を２で割った余りそれらの積が、7を２で割った余りに等しいかを計算したのですが、２以降3,4,5・・・nについても成り立つと思っていました。しかし、n=10,k=3,l=9,m=7のとき、3と9を３で割った余りの積0、7を３で割った余り1と両辺は一致しません。この場合￣ｋ×￣ｌ=￣ｍは3を10で割った余り、9を10で割った余りそれらの積が、7を10で割った余りに等しいかを計算したときだけ成り立つことを書いているのかがわかりません。￣ｋ×￣ｌ=￣ｍの具体的な計算を教えてください。またこの後が、2つめのわからない点です。互除法の原理 a,bを自然数とするaをbで割った余りがrのとき、(a,b)=(b,r) より(m,n)=(kl,n)=1もわかりません。m=kl-qn よりｍをnで割った余りkl(klはｎと互いに素)から、(m,n)=(n,kl)と考えました。kl≡m (mod n)より単純にｍをklに書き換えただけとも思いました。(m,n)=(kl,n)=1を説明してください。 本では、(m,n)=(kl,n)=1よりmもnも互いに素になります。ですから、×について閉じています。と続きます。
- 締切済み
- 数学・算数
- フェルマーの最終定理 N=3の場合
http://enjoymath.blog71.fc2.com/blog-entry-54.html この証明の後半のほうで （これより、2t, t+3, t-3は互いに素であるから） とありますが、なぜこれら３つの数が互いに素といえるのかが 分かりません。 （これより）、とは具体的にどの部分をさして、なぜ３つの数が互いに素になるのかの 詳しい解説をよろしくお願いします。
- ベストアンサー
- 数学・算数
補足
念のため確認ですが、ia とjaをbで割った余りが等しいと仮定する。と言う事をあなたは、言いたかったのですね。合っていますでしょうか？ご教授願いたいです。すみません。念のためです。