ユークリッドの互除法 & 素因数分解
最大公約数(Greatest Common Factor, GCF、または Greatest Common Divisor, GCD)とは、2つ以上の整数をいずれも割り切ることができる数(公約数)の中で最も大きい数のことです。数学において非常に重要な概念であり、分数の約分、比の計算、パターン分析など、さまざまな分野で活用されます。たとえば12と18を考えてみましょう。12の約数は1, 2, 3, 4, 6, 12で、18の約数は1, 2, 3, 6, 9, 18です。このうち共通して現れる約数は1, 2, 3, 6であり、最も大きい公約数である6が12と18の最大公約数です。最大公約数が1である2つの数は「互いに素(coprime または relatively prime)」と呼ばれ、これは1以外に共通の約数を持たないことを意味します。
ユークリッドの互除法(Euclidean Algorithm)は、紀元前300年頃にギリシャの数学者ユークリッドが著書「原論(Elements)」で紹介したアルゴリズムで、2000年以上にわたって使われ続けている最古のアルゴリズムの一つです。この方法は、大きな数の最大公約数も非常に高速に計算できるという利点があります。原理はシンプルです。2つの数 a, b(a > b)があるとき、a を b で割った余りを r とすると、GCD(a, b) = GCD(b, r) が成り立ちます。この過程を余りが0になるまで繰り返すと、最後に割った数が最大公約数になります。たとえばGCD(1071, 462)を求めると:1071 = 462 × 2 + 147 → GCD(462, 147) / 462 = 147 × 3 + 21 → GCD(147, 21) / 147 = 21 × 7 + 0 → GCD(21, 0) = 21。したがって最大公約数は21です。この方法の計算量は O(log min(a,b)) と非常に効率的です。
素因数分解とは、ある数を素数(prime number)の積として表すことです。この方法を使うと、最大公約数を体系的に求めることができます。手順は次のとおりです:① 各数を完全に素因数分解します。② 共通して現れる素因数を見つけます。③ 各共通素因数の指数のうち小さい値を選びます。④ 選んだ素因数をすべて掛け合わせます。たとえば72と48の最大公約数を求めると:72 = 2³ × 3² = 8 × 9 / 48 = 2⁴ × 3¹ = 16 × 3。共通の素因数は2と3であり、2の指数は min(3, 4) = 3、3の指数は min(2, 1) = 1です。したがって GCF = 2³ × 3¹ = 8 × 3 = 24 です。この方法は3つ以上の数の最大公約数を求めるときに特に便利で、各数の構造を明確に理解できるという利点があります。
最大公約数(GCF)と最小公倍数(LCM)には密接な関係があります。2つの自然数 a, b について、次の公式が成り立ちます:a × b = GCF(a, b) × LCM(a, b)。この公式を使えば、最大公約数がわかっているときに最小公倍数を簡単に求めることができます:LCM(a, b) = (a × b) / GCF(a, b)。たとえば12と18の場合:GCF(12, 18) = 6 / LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36。逆に最小公倍数がわかっているときに最大公約数を求めることもできます。素因数分解で理解するとより明確です。最大公約数は共通の素因数の最小の指数を使い、最小公倍数はすべての素因数の最大の指数を使います。12 = 2² × 3¹、18 = 2¹ × 3² のとき、GCF = 2¹ × 3¹ = 6(最小の指数)、LCM = 2² × 3² = 36(最大の指数)です。
最大公約数は日常生活のさまざまな問題を解決するのに役立ちます。1) タイル張りの問題:24cm × 36cm の長方形の床を正方形のタイルで隙間なく敷き詰めるには、タイル一辺の長さは GCF(24, 36) = 12cm でなければなりません。2) 分数の約分:18/24 を既約分数にするには、分子と分母を GCF(18, 24) = 6 で割って 3/4 に約分します。3) 比の単純化:48:72 の比を簡単にするには、GCF(48, 72) = 24 で割って 2:3 と表します。4) 分配の問題:りんご36個とオレンジ48個を同じ個数ずつ分けてギフトセットを作る場合、最大で GCF(36, 48) = 12 セット作ることができ、各セットはりんご3個、オレンジ4個で構成されます。5) 周期の計算:惑星Aは12年、惑星Bは18年の周期で公転する場合、2つの惑星が同じ位置で出会う周期は LCM(12, 18) = 36 年ですが、公約数である GCF(12, 18) = 6 年ごとに一定のパターンが繰り返されます。6) 歯車の設計:歯が24個の歯車と36個の歯車がかみ合うとき、GCF(24, 36) = 12 個ずつの区間に分けて設計すると、正確なかみ合わせを保証できます。
プログラミングにおいて、最大公約数はさまざまなアルゴリズムや暗号化技術に活用されます。再帰関数を用いたユークリッドの互除法の実装:function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } この簡潔な関数は非常に効率的に最大公約数を計算します。RSA暗号:公開鍵暗号システムであるRSAは、最大公約数が1である2つの数(互いに素)を見つける過程が核心です。2つの素数 p, q を選び、(p-1)(q-1) と互いに素な公開指数 e を選択します。画面解像度の比:1920×1080 解像度の比を求めると、GCF(1920, 1080) = 120 で割って 16:9 になります。分数演算の最適化:コンピュータで分数を扱う際、分子と分母を常に最大公約数で割って既約分数の形に保つと、オーバーフローを防ぎ、計算効率を高めることができます。有理数の判定:循環小数を分数に変換した後、約分する際に最大公約数を使います。ゲーム開発:タイルマップエディタでグリッドサイズを決めたり、キャラクターの移動速度を同期させたりする際に、最大公約数を活用して最適な基本単位を見つけます。