整数の有名な定理

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

自然数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'
で表すことができます。

投稿日時 - 2008-02-27 20:32:00