互除法の活用について

二つの整数a,bが互いに素であるとき
1 ap+bp=1を満たす整数p,qが存在する
2 任意の整数cについてax+by=cを満たす整数x,yが存在する

なぜ上記のようになるのか、よく理解できていないようです。具体例を考えてみれば、1についてはその通りになると納得できるのですが、文字を用いた一般的な式のままだと証明できず、今一掴めていないように感じます。
また、2に至ってはa,bが互いに素でなくとも成り立つのではと思ってしまいました。(例：a=2,b=4,x=1,y=1,c=6)どなたかご教授願います。

No.5 回答者： Ku-Mei 回答日時： 2017/01/24 22:58

1. について。

一般的に、a, b の最大公約数を d とすると、ax + by = d を満たす整数 x, y が存在する、ということがいえます（互助法を実行する過程を逆にたどって示されます）。

この結果を用いると、２は次のように簡単に示されます。

２．a, b が互いに素だから、その最大公約数は、１である。上に述べたことから、ax' + by' = 1 を満たす整数 x', y' が存在する。
この式の両辺に c をかけると、ax'c + by'c = c が得られる。
ここで、x = x'c, y = y'c として、ax + by = c を満たす整数 x, y が存在することが示された。

No.4 回答者： syotao 回答日時： 2017/01/24 22:26

一般に、ａ、ｂが互いに素ならばｘを0からｂ-1まで変えるとき、

ａｘをｂでわった余りは、0からｂ-1が１回ずつ出てくるという性質をもっています。
これを使って、2をつぎのように証明できます。

ｃをｂでわった余りをｒとすれば、ｃ＝ｂｑ＋ｒ（０≦ｒ≦ｂ-1）と書ける、
一方ａ、ｂが互いに素だから上の注意より、ｘを0からｂ-1までのどれかに選べば
ａｘをｂでわった余りはｒになる。
したがって、このえらびだしたｘについて　ａｘ＝ｂｑ’＋ｒと書けるから
この２式の辺々を引いてａｘ－ｃ＝ｂ(ｑ’－ｑ)　したがって
ａｘ－ｂ(ｑ’－ｑ)＝ｃ　だから　ｙ＝－(ｑ’－ｑ)とおけば
ax+by=cとなってこの方程式に整数解があるということになります。

まとめると、ａ、ｂが互いに素ならば
ｃがどんな整数でも、それをｂでわった余りｒは0からｂ－１の値であり
ｘを選んでaxをｂでわった余りをｒにできるから、
ax+by=c　はｃがどんな整数でも整数解をもちます。

No.3 回答者： syotao 回答日時： 2017/01/23 17:18

2について、

2は、a,bが互いに素であるとき、どんな整数cをもってきてもax+by=cを満たす整数x,yが存在する
といっているのです。
2ｘ＋4ｙ＝ｃで、ｃ＝6ならばたしかに整数解は存在します。
しかし、2ｘ＋4ｙ＝2(x+2y)＝偶数なのでｃが奇数ならば
2ｘ＋4ｙ＝ｃ　に整数解がないのです。
おなじようにして、もっと一般的に
a,bが互いに素でないばあい、ax+by=cに整数解がないような整数ｃが
あることもわかります。
それは、a,bが互いに素でないばあいax+byがa,bの1でない公約数の倍数になるからです。
なので、ｃがこの1でない公約数の倍数でないなら、
ax+by=cに整数解がありません。

No.2 回答者： クソgooは死ね 回答日時： 2017/01/23 04:50

差し出がましいようですが,

>1 ap+bp=1を満たす整数p,qが存在する
ここは, ap + bq = 1 を満たす整数 p, q が存在する, の書き間違いですよね.
有理整数環 Z において, (a) + (b) = (1) = Z を保証する, 重要な命題です.
(a) + (b) = (1) = Z は, 貴方が書いた 2 を保証します.

No.1 の回答者は, 整数論（といっても, 代数的整数論ですが）にもとても詳しい先生です.
この機会に, たくさん教わっておかないと損ですよ.
かじった程度の私は, これにて退散いたします.

No.1 回答者： Tacosan 回答日時： 2017/01/23 03:21

2 についてだけ: 例えば a = 2, b = 4, c = 1 としたら成り立ちますか?