[数学] 最大公約数ってなんだっけ？RSA 暗号を理解するまでの遠い道のり : 02

2024年11月14日 17:45

概要：この記事では RSA 暗号の仕組みを理解するための基礎的な事柄を説明していきます。小学生程度の算数の知識で理解できるように書いていきます。

今日学ぶこと

4 の約数は 1, 2, 4 です。4 を 1 で割っても，2 で割っても，4 で割っても，余りは 0 になります。割り切れます。このような数のことを約数といいます。

3は4 の約数ではありません。4 を 3 で割ったら，余りが 1 になるからです。

今，4 の約数と 6 の約数を考えてみます。

4の約数は以下のとおり。

$$
1, 2, 4
$$

6の約数は以下のとおり。

$$
1, 2, 3, 6
$$

図にしてみましょう。4の約数と 6 の約数で同じものがあります。1 と 2 です。同じ約数のことを，公約数といいます。そして，公約数のうち，一番大きいものを最大公約数といいます。今回の場合でいうと 2 です。

最大公約数を求める簡単な方法にユークリッドの互除法があります。下の記事に簡単にまとめてみました。