最大公約数の理解を深める：具体例で学ぶ互いに素の意味

最大公約数 (GCD) の概念は、整数の割り算の関係を理解するうえで重要です。ここでは a = g a’、b = g b’ の形を使い、a’ と b’ が互いに素である理由を具体例で説明します。

最大公約数の定義

整数 a, b に対して最大公約数 g = GCD(a, b) とは、a と b を同時に割れる最大の整数です。

例：a = 12、b = 18 の場合

まず GCD(12, 18) を求めます。12 の約数は 1,2,3,4,6,12、18 の約数は 1,2,3,6,9,18 です。共通する最大の約数は 6 なので g = 6 です。

a’ = a / g = 12 / 6 = 2、b’ = b / g = 18 / 6 = 3

このとき a’ と b’ の最大公約数は 1 です。つまり互いに素です。

もし a’ と b’ が 1 より大きい共通の約数 d を持つとすると、a = g a’ = g d x、b = g b’ = g d y となり、g*d が a と b を同時に割れることになります。これは g が最大公約数であることに矛盾します。

最大公約数 g を使って a = g a’、b = g b’ と表すと、a’ と b’ が互いに素であることは必須です。具体例を使うと、GCD の理解がより直感的になります。