今日のまとめ

• 2つの整数 $a$, $b$ に対して次の2つの集合は一致する：
  • $a x + b y$ ( $x$, $y$ は整数 ) の形で書ける整数全体の集合
  • 最大公約数 $\gcd(a, b)$ の倍数全体の集合
• 特に、$a$, $b$ を与えたとき、$a x + b y = \gcd(a, b)$ を満たす $x$, $y$ が必ず存在する。
• $a$, $b$ が互いに素ならば $a x + b y = 1$ を満たす $x$, $y$ が必ず存在する。

自宅学習の例

• $a=7^5=16807$ と $b=11^4 = 14641$ に対して $ax+by=1$ を満たす整数 $x$, $y$ をひと組みつけてみる。