アルゴリズム論特論（塩田）2021年度

Loading [MathJax]/jax/output/CommonHTML/jax.js

アルゴリズム論特論（塩田）第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 暗号をはじめとする公開鍵暗号の設計でとても重要になります。

前へ / 戻る / 次へ