最大公約数
$ \gcd
.
$ \gcd(a,b)=1
の時、
$ a,b
は互いに素
定理
正の整数
$ a,b
に対して、
$ \gcd(a,b)=ax+by
を満たす
$ x,y\in \mathbb{Z}
が存在する
これ、証明問題の材料として使ったりする
拡張ユークリッドの互除法