高校数学の問題です。回答おねがいします！

質問

自然数m、nについて、mとnの最大公約数が1であるとき、am+bn=1を満たす整数a、bが存在することを証明せよ。

回答No.7

B-juggler · ベストアンサー

Ｎｏ．３，５です。　(´・ω・`)

出てくるのはいいのですが（ありがたいことですね）、ちゃんと理解できるかは

難しいのではないかと思うのですが・・・。

最小公約数が１というだけなら、ダイジョウブなんでしょうね・・・。

ただ、この問題は、高校レベルで解けるのか？と、考えると、

ちょっと難しい気がするんです。厳密に証明しようと思うと、結構ねぇ・・・。

ざっと流してみるけど、分かるかな・・・？？

ｍ，ｎが互いに素　な自然数。　ａ，ｂを整数とする。
　＃これは定義です。

ｍ＞ｎ　としておきますね。これは便宜上。

ここからユークリッドの互除法をやっていきます。

ｍ＝ｑ0　×　ｎ　＋　ｒ1　　　　ｍをｎで割ってみる！まずね。ｑ　は　商ね。ｒはあまり。

ｎ＝ｑ1　×　ｒ1　＋　ｒ2　　　　ｎを　（ｍ／ｎ）のあまりで割ってみる！。

この二つをやって置いて、

ｒ1　＝　ｑ2　×　ｒ2　＋　ｒ3　　ｒ1をｒ2で割ってあげる。

ｒ2　＝　ｑ3　×　ｒ3　＋　ｒ4　　ｒ2をｒ3で割る・・・

ｒ3　＝　ｑ4　×　ｒ4　＋　ｒ5　　ｒ3をｒ4　以下同文・・・。
これを繰り返す～～。

ｒ ｎ＋１　＝　ｑｎ＋２　×　ｒ ｎ　＋０

　↑　ｎ＋１番目のあまりと、ｎ番目のあまりね。

ｒ ｎ＝１　となります。どこかで必ずね。互いに素ですからね。

もしも１でないとすると、　難しいので簡単化するよ？

ｒ4＝２だとします。　（ｒ5＝０　ね）

こうすると、ｒ3＝ｑ４　×　ｒ4　だから、　ｒ3　は２で割り切れる。

さかのぼっていくと、ｒ2　＝　ｑ3　×　ｒ3　＋　ｒ4

これも２で割り切れるね？　ｒ3は２の倍数だから。

ずっと遡ると、ｍ、ｎが２で割れてしまう。　互いに素に反するけね。

なので、互いにそのときは必ずどこかで、ｒ ｎ＝１となるところがあります。

で、今度は逆算をします。

１＝ｒ ｎ＝ｒ ｎ－２　－　（ｑｎ－１　×　ｒ ｎ－１）＝・・・・

　＝（ｎ－ｑ1　×　ｒ1）－ｑ3｛ｒ1－ｑ2（ｎ－ｑ1　×　ｒ1）｝

　ここで　ｒ1＝ｍ－ｑ0　×ｎ　を代入すると？

ちょっと分かりにくいかもしれないけれど、
　＃ここは実際に計算してみて欲しい。
ａ，ｂに当たるものは、ｑ　です。
　＃どっちか掛け算で、どっちか足し算！　になるから。

一般的にはこういう方法を使います。

一つ例を挙げよう、あまりに難しいと思うから。

どうしようか、ｍ＝６５　ｎ＝１９　にして見ますかね。
　＃１９が素数ですから互いに素。

６５　＝　１９×３　＋８　　８＝ｒ１ね　　３＝ｑ０

１９　＝　８×２　＋３　　　３＝ｒ２　　２＝ｑ１

ここから、ｒだけ。

８（ｒ１だね）＝３（ｒ２です）　×　２　＋２　　ｒ３＝２ね

３＝２×１　＋１　　ｒ４＝１

２＝１×２　＋０　　ｒ５＝０となりました。　ｒ４＝１なのでね。

３，２，２，１，２　これは商の部分を集めてみた。掛け算すると　２４ですね。

１になるところまでを足すと　３＋２＋２＋１＝７

どちらかマイナス、確かこれでいいはずだ。　足したほうがマイナスになるはず。

それが大きいほう（ｍ）にかかる。つまりはａだ。

ａ＝－７　、ｂ＝２４　となるはず。

ｍ＝６５　ｎ＝１９　だっけ？　－４５５＋４５６＝１かな？

こんな感じ。高校でこれ解けるならたいしたものだと思う。

一般の証明は大学生でも簡単じゃないよ～。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)　長文失礼。

回答No.6

中村 拓男（@tknakamuri）

調べて驚いたのですが、「互いに素」の概念は
小学校でも出てきますね。

遠まわしの表現ですが、「ふたつの数を最大公約数で割った数同士は、
1以外の公約数を持たない。」と教えてます。

回答No.5

B-juggler

Ｎｏ．３です。

＞Ｎｏ．４さん。えぇ！
互いに素　って言葉を使っていないだけで、実質互いに素ですね・・・。

この問題は高校で解ける？

互除法くらいしか一般化はできないんですよね・・・。

これ数論です。（代数学的数論に入るけれど）

Ｎｏ．２さんのも、半分なんですよ・・・。
左辺はあってるんですが、ｂｎについてやらないといけない。
それと、ａ，ｂ　の関連をつけないといけないです。
　＃背理法でやれば関連はつきますけれどね。

アルゴリズム使って解かせるかな？　と、一瞬思いましたが、
だめっぽいかな？

諸先生方～、高校レベルでいけるか助けて～。

σ(・・*)行けない気がします。

すごい人たちいるから、お願いします。ｍ（＿　＿）ｍ

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.4

中村 拓男（@tknakamuri）

>これは「互いに素」という概念を使う、大学の代数だけど？

高2の息子の宿題を時々手伝いますが、「互いに素」は
結構頻繁に出てきます。結構難しいです。
質問にあるように「最大公約数が1」という表現ですけどね。

回答No.3

B-juggler

代数学の元非常勤講師です。

Ｎｏ．１さん、中学入試でこれ出すところがある？すごいね、その中学。

これは「互いに素」という概念を使う、大学の代数だけど？

高校でこんなことやる？　だとしたら相当なものだよ？

　＃解ける高校生いるのなら相当なものだと思うけれど。

そうねぇ、どう書けばいいか、分からないよ。

この証明は大変だよ？？　Ｎｏ．１さんが書かれているとおり、

まず何が分からない　というのが分からないことには、こちらも答えようがないし。

そもそもこれを高校でやるか？

一応調べるために書くと、あなたが大学生だとしてね、これは理解できるだろうって

範囲で。

「ユークリッドの互除法」　で調べてみてくれるかな？

この状況で答えられることってこんなことしかないと思うけれどね。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.2

中村 拓男（@tknakamuri）

たぶん、あっていると思いますが・・・

1-am mod n は aを 1～n に変化させたとき全て異なる値になります。
もしそうでないなら modulo が一致するa の値 a1, a2 (|a1 - a2| < n) に対し

1-a1・m mod n = 1- a2・m mod n (a1≠a2) ⇒　(a1-a2)m は n の倍数となり、
互いに素の仮定と矛盾します。

なので、aを 1～n に変化させたとき余りが0の場合が必ずあるので

1-am = bn

となる a, b が存在します。

回答No.1

saki_nagatsuka

元塾講師です。

私立中学の入試問題で見た事があります。どこが分からないの？
試行錯誤のない登校はカンニングと同じです。とりあえず、やってみて
どこが分からないのかを記載しましょう。この投稿だとサボリにしか見えない。