gcd

質問

aとbの最大公約数を1とします。
ある十分大きい所より先の自然数は
aとbであらわせるのはなぜですか？

回答No.6

staratras

No.5です。数列の誤記の訂正です。失礼しました。

（誤）b行目:ba,ba+a,ba+2a,ba+3a,…

（正）b行目:ba,ba+b,ba+2b,ba+3b,…

回答No.5

staratras

＞ある十分大きい所より先の自然数はaとbであらわせるのはなぜですか？

互いに素（最大公約数が1)である自然数a,bについてa>bとして以下の、初項がa,2a,3a,…baですべて公差bの等差数列をb行考えます。

１行目:a,a+b,a+2b,a+3b,…
2行目:2a,2a+b,2a+2b,2a+3b,…
3行目:3a,3a+b,3a+2b,3a+3b,…
…
(b-1)行目:(b-1)a,(b-1)a+b,(b-1)a+2b,(b-1)a+3b,…
b行目:ba,ba+a,ba+2a,ba+3a,…

ここで各行の各項をbで割った余りを考えると、b,2b,3b,…はすべてbの倍数であることやa,bが互いに素なので最小公倍数がab(2数の積）であることなどから以下のことがわかります。

1.各行の項の余りはそれぞれの初項a,2a,3a,…(b-1)a,baをbで割った余りに等しい。
2.a,bは互いに素なので、１行目から(b-1)行目までの（a,2a,3a,…(b-1)aまでをbで割った）余りはすべて０ではない。
3.b行目に初めて割り切れて余りが０となる。
4.a,2a,3a,…(b-1)aまでをbで割った際のb-1個の余りはすべて相異なる。

上の4を示します。
m>nのとき、この中のm行目のmaとn行目のnaをbで割った余りrが等しいと仮定すると(1≦n<m≦b)
ma=Mb+r
na=Nb+r となるような自然数M,N(M>N)が存在することになります。
両辺同士を引くと
(m-n)a=(M-N)b ですが、仮定からb>m-n≧1 なので　
(m-n)a=(M-N)b<ab かつm-n,M-N は自然数から
aとbに最小公倍数ab(2数の積)よりも小さい公倍数が存在することになり、a,bが互いに素という条件に矛盾します。

よって上記の1行目からb-1行目まで等差数列は、それぞれbで割った余りが1からb-1までのすべてのいずれかの場合に１行ずつ過不足なく対応します。b行目は余りが0（bの倍数)の場合です。

またこのb行ある数列の初項のうちで最大なのはb行目のbaなので、少なくともab以上の自然数はすべてこの数列の項のどこかに登場することがわかります。ご質問の通り「ある十分大きい所より先の自然数」をすべて表すことができるということになります。

回答No.4

alice_44

任意の自然数 a,b について、その最大公約数を g と置くと、
ax+by=g …(1) を満たす整数 x,y が存在する。
a,b が素なら、g=1 だから、(1) を n 倍すると、a(nx)+b(ny)=n となる。
nx,ny を自然数または 0 に限定すると、
「ある十分大きいところより先の n」という制限がつく。

(1) を証明しておこう。
a,b のうち、小さくないほうを r[1]、大きくないほうを r[2] と置く。
r[1] を r[2] で割った余りを r[3]、
r[2] を r[3] で割った余りを r[4]、
…と、順に置いてゆく。
r[ ] は減少列だから、この操作はどこかで終わり、割り切れて
r[m]=0 となる m がある。r[m-1] が a,b の最大公約数である。
いわゆる「ユークリッドの互除法」だが、
r[ ] を定義する式を書き出してみると、
r[m-1]=r[m-3]-r[m-2]q[m-1],
r[m-2]=r[m-4]-r[m-3]q[m-2],
r[m-3]=r[m-5]-r[m-4]q[m-3],
…,
r[3]=r[1]-r[2]q[1].
となる自然数 q[ ] が在ることになる。
これらの式から、r[m-2],r[m-3],r[m-4],… を順次代入消去していくと、
最後に、r[m-1] が q[ ] と r[1],r[2] の式で表せる。
この式が、(1) である。

回答No.3

Tacosan

とりあえず a<b の場合だけ考えれば十分で, そのとき
任意の整数 k (0 ≦ k < a) に対して ax + by = k が 0 ≦ x < b かつ -a < y ≦ 0 であるような整数解を持つ
ことはいいでしょうか?

回答No.2

Tacosan

「aとbであらわせる」とは, どういうことですか?

補足

例えば、3と5のとき、
15以降の数が
15=3×5
16=3×2+5×2
17=3×4+5
...
みたいに、3と5倍数だけで,15以降の自然数すべてあらわせるのはなぜですか？

回答No.1

Kirby64

禅問答みたいやニャァ。

　aとbの最大公約数を２とします。
ある十分大きい所より先の自然数の半分はaとbであらわせるし、
　aとbの最大公約数を３とすれば、
ある十分大きい所より先の自然数の1/3はaとbであらわせると思うニャ。

　なんでやろうかニャァ？

補足

No.2の人の所に補足をかきました。