整数問題の疑問

よろしくお願いします。

a,bが異なる正の整数のとき、次のことを証明せよ。

（1）x,yがあらゆる整数値をとって変化するとき、ax+byの値はこの形で表される最小の正の整数dの倍数である。
（2）（1）におけるdはaとbの最大公約数である。


この問題自体は解けるのですが、ふと疑問に思ったのが、「この問題文の条件におけるd（つまり最小値）を論理的に求める方法はあるか」ということです。
たとえばa＝4 b＝8のときだとx＝-2 y＝1とすると値は0になり不適。幾つか試してみて4が最小値かなと思うのですが、本当に最小値であるか確かめる方法はあるでしょうか。
整数問題はバリエーションが豊富でもしかしたら知っているのに見落としているのかもしれません。
よろしければご教授ください。

No.5 回答者： fxq11011 回答日時： 2015/07/19 11:00

国語の理解力の問題かも、倫理的の。

この回答へのお礼

論理でしょうか。
ありがとうございます。

お礼日時：2015/07/29 13:35

No.4 回答者： kabaokaba 回答日時： 2015/07/19 01:40

これはとても有名で，

「ユークリッドの互除法」と呼ばれています．
dはaとbの最大公約数になります．
というか，これは最大公約数を求めるアルゴリズムです．

以下が成り立ちます

(1) a,bを互いに素な整数とすると，
適当な整数x,yが存在し，ax+by=1とできる
(2) a,bが整数，dをa,bの最大公約数とすると
任意の整数x,yに対して，ax+byはdの倍数

(1)が成り立てば(2)は自明ですので本質は(1)ですので
(1)を考えます．

a,bは互いに素とする
a>bとしても一般性を失わない
a=bq+r (0 <= r< b-1)と割り算をする
これを (a,b) -> (b,r) と表記することにする
次に，同様に
b=r q1 + r1 (0 <= r1 < r-1)
と割り算し，これをまた同様に (b,r) -> (r, r1) と表記する
これを繰り返す．
(a,b) -> (b,r) -> (r,r1) -> (r1,r2) -> ・・・
ここで数の列b,r,r1,・・・は
b>r>r1＞・・・＝>0とかならず小さくなるので（割り算の余りだから）
0になって終わることになる
0の直前の数をdとする
列の最後の部分
(r'',r') -> (r',d) -> (d,0)
を考えると適当な整数qとq'を用いて
r' = d q + 0
r''=r' q' + d (0<= d < r''-1)
であるので，
r'' = dqq' + d = d(qq'+1)
つまり，dはr'とr''の公約数
ここで列の途中(s,t) -> (t,u)において
s=t p + u (pは整数)
とできるので，tとuの公約数はsとtの公約数でもあることに注意すれば，
上記のdは最終的にはaとbの公約数でもあることがわかる．
a,bは互いに素なのでd=1である

さて・・・
(a,b) -> (b,r) -> (r,r1) -> (r1,r2) -> ・・・ ->(d,0)
のことですが

12 と 9 でやると
(12,9) -> (9,3) -> (3,0)
なので，証明のdは3でこれは最大公約数
a,bが互いに素ではないとき，dは最大公約数になります．

上の証明ではa,bを互いに素としたのでd=1と結論しましたが
a,bが互いに素としない場合・・・
d'をdよりも大きな公約数とした場合
ｄ’がdの約数になるという事態に陥ります

これは
列の途中(s,t) -> (t,u)において
s=t p + u (pは整数)
とできるので
s,tの公約数はt,uの公約数でもあることに注意すれば
(r'',r') -> (r',d)
の部分でｄ’がdの約数になることからわかります．矛盾です

この回答へのお礼

ユークリッド互除法と同値の式だったのですね。
結局互いに素でない数を入れても括ることで同じ形を作ることができるのですね。

ありがとうございました。

お礼日時：2015/07/29 13:36

No.3 回答者： rabbit_cat 回答日時： 2015/07/19 01:02

＞「この問題文の条件におけるd（つまり最小値）を論理的に求める方法はあるか」

あなたの疑問は、問題の(2)そのものだと思うのですが、
＞この問題自体は解けるのですが、
と言っている。じゃあ何が疑問なんですか？? (2)は本当に解いたのですか？

ちなみに、(2)は非常に有名な定理
aとbが互いに素 ⇔ ax+by=1が整数解(x,y)を持つ
というやつです。この定理自体（とくに、aとbが互いに素 ⇒ ax+by=1が整数解を持つ）は、背理法を用いて証明します。
簡単に概要を書けば、
・ a,2a,…,(b-1)a を bで割った余りは全て異なる（もし、i×aとj×aをbで割った余りが互いに等しければ、(i-j)×aはbで割り切れる ⇒ aとbが互いに素なことに矛盾する）
また、
・任意の整数を、正の整数bで割った余りは、0～b-1までのb通りしかない、
というわけで、
・ a,2a,…,(b-1)a の中にbで割った余りがちょうど１になるものが存在する
したがって、
m×a = n×b + 1
なる、整数n,mが存在する、(x,y)=(m,-n)とおけばよい
みたいな感じです。

No.2 回答者： w_letter 回答日時： 2015/07/18 23:59

4x+8y

＝4(x+2y)

ここで、x,yは、整数値であるから、(x+2y)は、整数値である。

したがって、(x+2y)が１であるとき、最小の正の整数d=4である。

例えば、x＝3, y＝-1や、x＝-1, y＝1や、x＝-99, y＝50・・・・無限に存在します。

こんな説明で、よかったでしょうか？

この回答へのお礼

やはり括ることで部分的に互いに素な組を作ることができるのですね。
納得しました。
ありがとうございます。

お礼日時：2015/07/29 13:37

No.1 回答者： w_letter 回答日時： 2015/07/18 21:11

＞（1）x,yがあらゆる整数値をとって変化するとき、ax+byの値はこの形で表される最小の正の整数dの倍数である。

a=1,b=2,x=-1，y=1

だと・・・・・ax+byの値は、１になるけど・・・

最少の正の整数は１だから・・・確かめる必要はないけど・・・

それと、

＞x＝-2 y＝1

だと・・・・ｙ=-1/2になるから、整数値じゃないんだけど・・・・

もしかして、子ブたん、なんかかんちがいしてる？？？？

この回答へのお礼

回答ありがとうございます。

a,bは定数で、その度に設定される数字、x,yは変数である定数a,bが定まった上であらゆる整数に変化する、という認識ですが、誤りでしょうか。
その解釈の上で今回はa＝4,b＝8とした場合のax+byの最小値は4では、というつもりでした。
また、x＝-2 y＝1はx＝-2,y＝1というつもりです。
わかりづらくすみません。

お礼日時：2015/07/18 21:31