線形結合…^^;

よく出る問題なんだけどその背景がすぐわからず…^^;

 http://www004.upp.so-net.ne.jp/s_honma/relax/sum10.htm ;より 引用 Orz〜

「『ａ 、 ｂ を互いに素な自然数とする。０以上の整数 ｘ 、 ｙ を使って ａｘ＋ｂｙ の形で表すことができない最大の整数を求めよ。』

 

 

（証明）　

ｂ＞ａ として考える。0以上の整数 ｘ、ｙ を使って、ａｘ＋ｂｙ の形で表される数の集合

 

をＡとする。１から順に ｂ 個毎に行を変えながら ａｂ まで書く。

 

　　1　　 2　　3　 …　　b

　 b+1　 … 　… 　… 　2b

　 ・　　　　　　　　　 ・

　 ・　　　　　　　　　 ・

　 ・　　　　　　　　　 ・

(a-1)b+1 … 　… 　… 　ab

 

a の倍数に着目したとき、a の倍数は各列1つしか現れない。

 

実際に、任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　

（ｋは自然数で、１≦ｋ≦ｂ）において、ある自然数 ｍ、ｎ （１≦ｍ＜ｎ≦ａ）が存在して、　

ｍｂ＋ｋ≡ｎｂ＋ｋ　（ｍｏｄ　ａ）　が成り立つと仮定すると、

 

（ｍ−ｎ）ｂ≡０　（ｍｏｄ　ａ）　で、（ａ，ｂ）＝１　より、　

ｍ−ｎ≡０　　（ｍｏｄ　ａ）　となる。

 

しかるに、これは、　１≦ｍ＜ｎ≦ａ　に矛盾する。

 

したがって、ａ個の任意の列　ｋ、ｂ＋ｋ、２ｂ＋ｋ、・・・、（ａ−１）ｂ＋ｋ　の各項を ａ で割った余りは全て異なる。

このとき、この列の項で、ａ で割り切れるものがただ一つ存在する。

 

右端の列、即ち、ｂ で割り切れる数はすべてＡに入っている。

それ以外の列は、どこかでａ の倍数が現れ、それ以後はすべてＡに入る。

 

ａ の倍数は各列1つしか現れないので、最後にＡに含まれる列は、ａ(ｂ−１) が含まれる列

 

なので、表すことの出来ない最大の数は、その１行前の数字 ａ(ｂ−１)−ｂ＝ａｂ−ａ−ｂ　と

 

なる。（証終）

 

『ａ、ｂ を互いに素な自然数とする。０以上の整数 ｘ、ｙ を使って ａｘ＋ｂｙの形で表すことができない自然数の個数を求めよ。』

 

（解）　ａ、２ａ、３ａ、・・・、（ｂ−１）ａ　の各数を ｂ で割った余りは、１、２、３、・・・、ｂ−１ の何れかで、互いに１対１に対応する。このとき、求める場合の数は、

 

［｛ａ＋２ａ＋３ａ＋・・・＋（ｂ−１）ａ｝−｛１＋２＋３＋・・・＋（ｂ−１）｝］/ｂ

 

　＝（ａ−１）｛１＋２＋３＋・・・＋（ｂ−１）｝/ｂ

 

　＝（ａ−１）（ｂ−１）/２

 

で与えられる。

 

したがって、ａｘ＋ｂｙ の形で表すことができない自然数の個数は、

 

　　　　　　　(a-1)(b-1)/2