アルゴリズム論特論（塩田）　2015年度教材

アルゴリズム論特論（塩田）　2015年度教材　第3回

授業内容
- てんびんクイズ
  - 十分大きな天秤と、a グラムと b グラムの分銅がたくさんあるとき、測ることのできる最小の重さはいくらか？
- 最大公約数 gcd, 最小公倍数 lcm
ツボ
- 2つの自然数 a, b に対して次の2つの集合は一致する：
  - a x + b y ( x, y は整数 ) の形で書ける整数全体の集合
  - gcd(a, b) の倍数全体の集合
- 特に、a, b を与えたとき、gcd(a, b) = a x + b y を満たす x, y が必ず存在する。

宿題
- 下記の場合については gcd(a,b) = 1 であることがわかっている。それぞれ a x + b y = 1 を満たす整数の組 (x, y) をひとつ求めてみよ。（無理な場合は潔く諦めよ。）