逆に「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)となるところがわかりません。それと、0<jーi<bかつ(jーI)a
は、bの倍数になることと、なぜそれで、a とbが互いに素になることに矛盾するのでしょうか?ご教授願いたいです。すみません。
の文章で、なぜ、bで割った余りが、ia とja にできるのかが分かりません。ご教授願いたいです。すみません。
A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
ここでは、何か特定の数字を示して居ません。
だから、i j も m n も 順番の特定の数字を示しているものではありません。
④ の説明の言葉通りに固定的に考えると、一見、異なるように思えますが、
質問は、互いに素となる自然数を a b としており、
しかも、ia ja は、aの倍数。しかも、アルファベット順に数字が大きくなっているならば、iaとja(ただしi<j)で正しいですが、
その次の説明 0<j-i が正しければ、0>j-i としなければなりませんから、答えは無いか、記載が間違っています。
つまり、この問題そのものに矛盾がある場合には、解は得られないという意味です。
さらに、④では、互いに素となる自然数を m nとしましたから、記号は変わっても、同じ概念という意味です。
つまり、i=3 j=7でも m=3 n=7 でもよく、数字を文字に置き換えることを代数と言います。
但し、中国余剰定理は、優れた概念と計算処理方法だとは思いますが、全てに単純に応用できるものではなく、これを使用するには、条件があるようですから、適用条件と基本となる数学の考え方を知らないと、この高等数学はうまく使えない様に思います。
例えば 互いに素というのは言い換えれば,共通の素因数を持たないという意味です。
5で割って2余る数 7で割って2余る数は何か?
これは37ですよね。
但し、35と5になると、35は、7でも5でも割れますから、互いに素にはなりませんね。
このように、中国剰余定理で解くことができるものは、条件が揃って初めて解が得られるので、条件を丁寧に確認すること、さらに、何故、中国剰余定理で解く必要があるのかを考えることが大事だと思います。
理由は、言葉の定義を含めて、数学は、ある概念についての論理的な考え方の展開だからだと思うからです。
逆に「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)となるところがわかりません。それと、0<jーi<bかつ(jーI)a
は、bの倍数になることと、なぜそれで、a とbが互いに素になることに矛盾するのでしょうか?ご教授願いたいです。すみません。
の文章で、なぜ、bで割った余りが、ia とja にできるのかが分かりません。ご教授願いたいです。すみません。
では、これは、嘘なのでしょうか?ご教授願いたいです。すみません。
No.3
- 回答日時:
bで割った余りが、ia やja になるのか?
数学的な理解の前に、文章の理解だと思います。
つまり、
条件
① 「aとb が互いに素」であるならば,
② bで割った余りが同じものがあれば
③ iaとja(ただしi<j)として,0<j-i<bかつ(j-i)aはbの倍数
④ 但し③は、aとb が互いに素であることと矛盾
⑤ a,2a,3a,...,(b-1)aをbで割った余りはすべて異なる
⑥ 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=(15)の時 bで割ると余り1
上記、bで割る数は、全て、a の倍数
∵ j や i は a がついているから #1の④のmnと同じ。
No.2
- 回答日時:
中国剰余定理というのは、プログラミングの思考形式みたいなもの。
④ m で 割った余りが a で,n で割った余りが b であるような整数が必ず存在する。 しかも,その ような整数を mn で割った余りはすべて等しい。
の意味は、「最終的に余りは、異なる」という意味の観ている数字と、ここに書いた mのa nのb mnのm+n という意味
具体的には、1 以上 100 以下の整数で考える場合、「3 で割ったあまりが 2」かつ「5 で割ったあまりが 3」という条件は、「15 で割ったあまりが 8」という条件と同値になりますよね。 紙に書いてみてもわかるけど。
これを、
中国剰余定理では
x≡2 (mod.3)
x≡3 (mod.5)
x≡8 (mod.15) と書きます。
つまり、この場合、余りの数そのものは異なるけれども、そこには一定の法則により共通の数が存在するということですね。
言い換えれば、
x≡2 (mod.3) =㋑として
x≡3 (mod.5) =㋺として
x≡8 (mod.15) =㋩とすると
23という数字は、8で割ると15余り 3で割ると7回後に2余り 5で割ると4回後に3余りますよね。 つまり15で割った余りの数は、3+5ですよね。
しかも、解き方にルールがあるから、そのルールを知らないと、数式を立てたり、解いたりすることができず、了解不能になりがちですね。その点は、厄介。但し、判れば、高速計算が可能になるらしい。
では、なぜ、bで割った余りが、ia やja になるのでしょうか?これについて余りが同じになるというのは、どういう事でしょうか?ご教授願いたいです。すみません。
No.1
- 回答日時:
「〜で割ったあまりが〜である」という複数の条件が、単一の条件にまとめ上げられた状態の時に、中国剰余定理を使うことができると主張するもののようなので、優れた手法ではあると思いますが、条件に当てはまらないものは、他の定理と同じように、うまく使えないことがあるのではないでしょうか?
① 基本的な疑問
0<jーi ということは、i <jでなければ、マイナㇲになるので、0より大きくなりませんよね。
② (j-i)aはbの倍数 の ヒント
二元の場合において n1 と n2 が『互いに素でない場合』
〇lcm(n1,n2) は n1 と n2 の最小公倍数,gcd(n1,n2) は n1 と n2 の最大公約数を表し
〇n1 と n2 が互いに素なときは,gcd(n1,n2)=1 となり常に右側の条件が満たされるので二元の場合の中国剰余定理と一致
③ a とbが互いに素になることに矛盾
②により、互いに素で無いから。
④ bで割った余りが、ia とja にできるのか ヒント
m, n を互いに素な自然数,a, b を 0 < = a < m, 0 < = b < n となる整数とするとき,m で 割った余りが a で,n で割った余りが b であるような整数が必ず存在する。 しかも,その ような整数を mn で割った余りはすべて等しい。 これを中国の剰余定理と呼ぶ
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 数II 剰余の定理と因数定理 整式P(x)をxで割った余りが-4,x-2で割った余りが7である。 P 2 2022/07/03 13:38
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- 数学 中2 数学 8 2023/06/27 21:56
- その他(教育・科学・学問) 小学生の算数の商について 3 2023/03/06 14:11
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 中学校 都立入試 0 2022/10/04 19:37
- 数学 代数の質問です 2 2022/04/30 14:10
- 大学受験 合同式 1 2022/09/03 12:37
- 数学 教えてください。 2 2022/06/30 14:26
- 大学受験 合同式 2 2022/08/19 13:12
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
傘を買うと雨は止む。
-
定理と法則の違い
-
数IIIの定理、受験で使っていい...
-
東大編入問題です。 この(3)の...
-
11・13y≡5(mod9)がy≡4(mod9)にな...
-
数A nは自然数とする。n , n+2 ...
-
4色定理と5人の王子様の解に...
-
整列集合の比較定理
-
定義と定理について
-
3点が一直線上である証明
-
二次合同式の解き方
-
11の22乗を13で割った余り...
-
大学数学 解答
-
x^100を(x+1)^2で割ったときの...
-
ハムサンドイッチの定理や平均...
-
aは自然数とする。a+5は4の倍...
-
至急です! 数学で証明について...
-
直角三角形じゃないのに三平方...
-
複素幾何の予備知識
-
ほうべき(方巾)の定理について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
大学の記述入試で外積は使えま...
-
至急です! 数学で証明について...
-
パップスギュルダンの定理について
-
直角三角形じゃないのに三平方...
-
【遊びのピタゴラスイッチはな...
-
定理と法則の違い
-
lim[x→+∞](x^n/e^x)=0 の証明
-
フーリエの積分定理がわかりません
-
完全数はどうして「完全」と名...
-
中学2年図形の証明についての質...
-
ピタゴラス数について。
-
ほうべき(方巾)の定理について
-
大学数学 解答
-
【線形代数】基底、dimVの求め方
-
相似比の答え方・・・
-
aは自然数とする。a+5は4の倍...
-
4色定理と5人の王子様の解に...
-
複素幾何の予備知識
-
十分性の確認について
-
拡張ユークリッド互除法による...
おすすめ情報