参考書に載っていた命題の証明で分からない部分がありました。
命題:a,bが0でない整数のとき「ax+by=1を満たす整数x,yが存在する⇔aとbは互いに素」
(⇐の証明)
a,bは互いに素であるから、「a,bは互いに素な自然数とするとき、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる」という定理から、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる。ここで、整数をbで割ったときの余りは0,1,2,……,b-1のいずれかでb通りあるから、akをbで割った余りが1となるような整数k(1≦k≦b)が存在する。
akをbで割った商をl(エル)とすると
ak=bl+1、すなわちak+b(-l)=1
よって、x=k,y=-lはak+by=1を満たす。
すなわち、ax+by=1を満たす整数x,yが存在することが示された。
a,bは互いに素であるから、「a,bは互いに素な自然数とするとき、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる」という定理から、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる。
とありますが、この命題ではa,bについては0ではない互いに素な整数であることは分かっていますが、どちらも負の数またはどちらかが負の数であることもあり得ると思います。
その時にもこの定理は成り立つといえるのでしょうか。また、成り立つとしても、その証明を書かずして「b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる」に帰結してしまってよいのでしょうか。
No.2ベストアンサー
- 回答日時:
あのー、a>0、b>0のとき、成立つのを仮定すれば、
たとえば、a<0、b>0のときは、|a|x+by=1に整数解x、yがあるのだから
a(-x)+by=-ax+by=|a|x+by=1
となって、この場合にも整数解のあることが分かります。
また、aもbも負のときは、|a|x+|b|y=1に整数解x、yがあるのだから
a(-x)+b(-y)=1 となって、この場合にも整数解があります。
つまり、a、b両方が正のとき証明できたら、a、bどっちかもしくは両方負でも証明できるのです。
(⇐の証明)
a,bは互いに素であるから、「a,bは互いに素な自然数とするとき、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる」という定理から、
a、bが自然数の場合、
b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる。ここで、整数をbで割ったときの余りは0,1,2,……,b-1のいずれかでb通りあるから、akをbで割った余りが1となるような整数k(1≦k≦b)が存在する。
akをbで割った商をl(エル)とすると
ak=bl+1、すなわちak+b(-l)=1
よって、x=k,y=-lはak+by=1を満たす。
すなわち、a,bが自然数であるときとax+by=1を満たす整数x,yが存在することが示された。
したがって……
この続きからsyotaoさんが書いてくださったように、直前の結論を利用してa,bが共に自然数でないときにもax+by=1を満たす整数x,yが存在することを示せばよいでしょうね。脱帽です。これなら簡単に証明、説明できますね。「a,bは互いに素で少なくともどちらか一方が負の数であるとするとき、b個の整数a・1,a・2,a・3,……abをそれぞれbで割った余りはすべて異なる」ということが成り立つか証明することにこだわらなくても良かったのか……。この度は回答をありがとうございました。
No.1
- 回答日時:
厳密にいうと、定理は自然数について述べていますので、
双方がマイナスの場合と片方がマイナスの場合について証明すべきかもしれません。
ぶっちゃけ、a、bのどちらか、もしくは片方がマイナスであった場合、
それらの正の数 a'、b'において、それぞれx'、y'が存在することは証明できます。
あとは、a'x' = ax, b'y'=by (-符号だけ移行させる)とaxとbyについても証明できますが、
それを自明とすべきかどうかは、よくわかりません。
負の数の割り算のあまりの数をどう定義するかって問題にもなりますので、
一応述べておいたほうが良いかもしれません。
定義ではなく定理を自明にするかしないか、というのは問題を解いていてよく迷ったり悩んだりしてしまうのですよね。負の余りを出すと長くなってしまいそうなので、簡単な方で理解し述べておこうと思います。この度は回答をありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
大学の記述入試で外積は使えま...
-
【遊びのピタゴラスイッチはな...
-
至上最難問の数学がとけた
-
傘を買うと雨は止む。
-
交代式の性質
-
3以上9999以下の奇数aで、(a^2)...
-
4.6.8で割るとあまりはそれぞれ...
-
直角三角形じゃないのに三平方...
-
ほうべき(方巾)の定理について
-
数A nは自然数とする。n , n+2 ...
-
lim[x→+∞](x^n/e^x)=0 の証明
-
【線形代数】基底、dimVの求め方
-
Xの3乗+Yの3乗=Zの3乗
-
ハムサンドイッチの定理や平均...
-
△ABCの∠Aの2等分線と辺BCとの交...
-
数の歴史
-
数学の問題でわからないところ...
-
パップスギュルダンの定理について
-
定理と法則の違い
-
至急です! 数学で証明について...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
至上最難問の数学がとけた
-
【遊びのピタゴラスイッチはな...
-
大学の記述入試で外積は使えま...
-
lim[x→+∞](x^n/e^x)=0 の証明
-
直角三角形じゃないのに三平方...
-
数学が大好きな国の国旗のデザイン
-
数Aの図形の性質の3の問題につ...
-
パップスギュルダンの定理について
-
複素積分の
-
定理と法則の違い
-
ファルコンの定理は解かれまし...
-
実数の整列化について
-
数A nは自然数とする。n , n+2 ...
-
【線形代数】基底、dimVの求め方
-
コーシーの積分定理 複素積分
-
完全数はどうして「完全」と名...
-
ほうべき(方巾)の定理について
-
「整数係数方程式の有理解の定...
-
長さがマイナスの答えのとき、...
-
傘を買うと雨は止む。
おすすめ情報