「ax+by=1を満たす整数x,yが存在する⇔aとbは互いに素」という命題の証明

参考書に載っていた命題の証明で分からない部分がありました。

命題：a,bが０でない整数のとき「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で割った余りが１となるような整数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.1 回答者： ShowMeHow 回答日時： 2017/03/16 13:45

厳密にいうと、定理は自然数について述べていますので、

双方がマイナスの場合と片方がマイナスの場合について証明すべきかもしれません。

ぶっちゃけ、a、ｂのどちらか、もしくは片方がマイナスであった場合、
それらの正の数　a'、b'において、それぞれx'、y'が存在することは証明できます。
あとは、a'x' = ax, b'y'=by (-符号だけ移行させる）とaxとbyについても証明できますが、
それを自明とすべきかどうかは、よくわかりません。
負の数の割り算のあまりの数をどう定義するかって問題にもなりますので、
一応述べておいたほうが良いかもしれません。

この回答へのお礼

定義ではなく定理を自明にするかしないか、というのは問題を解いていてよく迷ったり悩んだりしてしまうのですよね。負の余りを出すと長くなってしまいそうなので、簡単な方で理解し述べておこうと思います。この度は回答をありがとうございました。

お礼日時：2017/03/17 01:38

No.2 ベストアンサー 回答者： syotao 回答日時： 2017/03/16 15:57

あのー、ａ＞0、ｂ＞0のとき、成立つのを仮定すれば、

たとえば、ａ＜0、ｂ＞0のときは、|ａ|ｘ＋ｂｙ＝1に整数解ｘ、ｙがあるのだから
ａ(－ｘ)＋ｂｙ＝－ａｘ＋ｂｙ＝|ａ|ｘ＋ｂｙ＝1　
となって、この場合にも整数解のあることが分かります。
また、ａもｂも負のときは、|ａ|ｘ＋|ｂ|ｙ＝1に整数解ｘ、ｙがあるのだから
ａ(－ｘ)＋ｂ(－ｙ)＝1　となって、この場合にも整数解があります。
つまり、ａ、ｂ両方が正のとき証明できたら、ａ、ｂどっちかもしくは両方負でも証明できるのです。

この回答へのお礼

（⇐の証明）
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で割った余りが１となるような整数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で割った余りはすべて異なる」ということが成り立つか証明することにこだわらなくても良かったのか……。この度は回答をありがとうございました。

お礼日時：2017/03/17 01:46