解説
- a, b を正の整数 (a > b) とし、aをbで割った商をq, 余りをrとするとき、aとbの最大公約数は, bとrの最大公約数に一致する。
- すると、こんな問題の解を、一定の手続きで求めることができる。
- a = 1058, b = 943の最大公約数はいくつか （絶望的な気持ちになるのでは）
- 943/1058 は、約分できるか？ （2はダメっぽい。3もダメだ、、、とやるのは大変）
- [解答例]
- 1058と943の最大公約数は、1058 ÷ 943 = 1 余り 115だから、943と115の最大公約数に等しい。
- 943と115の最大公約数は、943 ÷ 115 = 8 余り 23だから、115と23の最大公約数に等しい。
- 115と23の最大公約数は、115 ÷ 23 = 5 余り 0 だから、115と23の最大公約数は、23である。
- すると、943と115の最大公約数、1058と943の最大公約数は、23である。
- また、943/1058は、最大公約数23で約分すると、41/46である。
証明
- a, b を正の整数 (a > b) とし、aをbで割った商をq, 余りをr とする。
- a = bq + r だから、bとrの公約数は、aの約数である。
- よって、bとrの公約数は、aとbの公約数でもある。･･･ （１）
- r = a - bqであるから、aとbの公約数は、rの約数である。
- よって、aとbの公約数は、bとrの公約数でもある。･･･ （２）
- （１）、（２）より、次のことが成り立つ
- aとbの最大公約数は、bとrの最大公約数に一致する。
- a, b を正の整数 (a > b) とし、aをbで割った商をq, 余りをr とする。
- a = bq + r だから、bとrの公約数は、aの約数である。 (bとrを割ることができるから、その数をmとするとa = m(b/m*q +
r/m)とできる。b/m, r/mは整数である）
- よって、bとrの公約数は、aとbの公約数でもある。 (mは、bを割れる（rを割れる）。さらにaも割れる、ということで、どんなmも、aとbの公約数。ただし、aとbの公約数でも、bとrの公約数ではないものもあるかもしれない） ･･･ （１）
- r = a - bqであるから、aとbの公約数は、rの約数である。(aとbを割ることができるから、その数をnとすると、r = n(a/n -
b/n*q)とできる。a/n, b/nは整数である）
- よって、aとbの公約数は、bとrの公約数でもある。(nは、bを割れる(aを割れる）。さらにrも割れるということで、どんなnもbとrの公約数。ただし、bとrの公約数でも、aとbの公約数ではないものもあるかもしれない） ･･･ （２）
- （１），（２）より、次のことが成り立つ （両方成り立つということは、aとbの約数全体とbとrの約数全体はぴったり一致する。だから）
- aとbの最大公約数は、bとrの最大公約数に一致する。
不定方程式
- 1つの箱には12本の鉛筆が入っている。いくつかの箱を開けて、鉛筆をすべて外に出した。これらの鉛筆を41人の生徒に同数ずつ配ったところ、3本余った。各生徒に配る鉛筆が最小の場合、1人に何本を配ったことになるだろうか。
- 12x - 41y = 3 （１） を満たす整数解のうち、最小のyを求めよ、という問題
[解答]
- 12と41の最大公約数を求める。
- 41 = 12 * 3 + 5 （２）
- 12 = 5 * 2 + 2 （３）
- 5 = 2 * 2 + 1 （４）
- 2 = 1 * 1 + 1
- 1 = 1 * 1 + 0 従って、最大公約数は1である。
- この式を逆に辿ってみる。
- 1 = 5-2*2 （４）’
- 2 = 12 - 5*2 （３）’
- （３）’を（４）’に代入すると、1 = 5 - (12-5*2)*2
- 5 = 41 - 12 *3 （２）’
- （２）’を（５）に代入すると、1 = (41 - 12*3)*5 - 12*2
- 1 = 41 * 5 - 12 *17
- 12 * (-17) + 41 * 5 = 1
- 3倍すると、
- 12 * (-51) + 41 * 15 = 3 （６）
- （１） - （６）
- 12(x +51 ) - 41(y+15) = 0
- 12 (x + 51) = 41 (y +15)
- 12と41は、互いに素だから、kを整数とすると
- x + 51 = 41k, y +15 = 12k
- xとyが正の数で、yが最小の整数になるには、k=2のときで、y =9である。
引き算でも求めることができる