整数の有名な定理

質問

a,bがと互いにそのとき、ab+1以上の「全ての自然数」はax+byで表すことが出来る。

この事実がテーマになった問題があり、参考として証明が書いてありましたが、なぜab+1以上なのかは書いてありませんでした。前提のようになっていました。

大学受験では必要ないですが気になるので一応教えてください。それともこういうことは捨てたほうがいいでしょうか。

「負でない整数」に変えるとab+1-a-b居所となっていることもなおさらわかりません。

教えてください。

回答No.2

age_momo · ベストアンサー

きちんと書くと長くなりますので道筋だけ

自然数a,bが互いに素ならユークリッド互助法を用いて
最大公約数(=1)が求まります。これを拡張すると
am+bn=1
となる整数の組(m,n)が必ず存在することを表します。
例えば適当な数字ですが18,41は互助法で

41-18*2=5
18-5*3=3
5-3=2
3-2=1
3-(5-3)=3*2-5=(18-5*3)*2-5=18*2-5*7
=18*2-(41-18*2)*7=18*16-41*7
=18*16+41*(-7)=1

です。ここで0<m<bならば-a<n<0、-b<m<0ならば0<n<aです。
つまり、0<m<b,0<n<aであるm,nを用いて
am-bn=1
と表せるということです。後は両辺にabを足して
am+b(a-n)=1+ab
a>nですから自然数m,(a-n)を用いてab+1が表せたことになります。
次にab+kは
a(km)-b(kn)=k
knをaで割ったときの商をp,余りをqとすると
a(km-pb)-b(kn-pa)=a(km-pb)-bq=k
　　　ここでa(km-pb)=k+bq>0よりkm-pb>0です。
両辺にabを足すと
a(km-pb)+b(a-q)=ab+k
qはaで割った余りですからq<aで、(a-q)>0です。
よって
ab+1より大きい数字は自然数am+bnで表せます。

自然数m,nを用いてab+1以上の整数を表すことができましたから
非負整数を用いて例えばab-a-b+1を表したいのなら
am+bn=ab+1
両辺から(a+b)を引いて
a(m-1)+b(n-1)=ab-a-b+1
m,nは自然数でしたから(m-1),(n-1)は非負整数です。
よってab-a-b+1以上の整数は非負整数m',n'を用いて
am'+bn'
で表すことができます。

回答No.1

Quattro99

http://oshiete1.goo.ne.jp/qa3426536.html
に関連しているのでは？
ab+1以上ならかならず表すことが出来ることを示すことで、表せない自然数を考える場合にab以下の自然数だけに絞ればよいということを示すために出てきたものなのではないでしょうか。