アルゴリズム論特論（塩田）第2回 (4) 互いに素
互いに素
Def.10 $\gcd(a,b)=1$ のとき、$a$ と $b$ は互いに素であると言う。
「どちらも素数」という意味では
ありません。恥ずかしいので間違えないように。
Th.11 $a$, $b$ が互いに素ならば
$ax+by=1$
を満たす $x$, $y$ が存在する。
Th.12 $a$, $b$ が互いに素、かつ $b \times c$ が $a$ の倍数ならば、$c$ が $a$ の倍数。
証明 Th.11 より $ax+by=1$ を満たす $x$, $y$ を取ると
$c = 1 \times c = (ax+by)c = a(cx) + (bc)y$
となり、$bc$ が $a$ の倍数ゆえ右辺は $a$ の倍数です。(証明終)
※ $\gcd$ や、Th.11 の $x$ が、RSA 暗号をはじめとする公開鍵暗号の設計でとても重要になります。