最大公約数
2つの整数の最大公約数とは、両方の数を割り切る数で、しかもそれより大きい数で両方を割り切るものがないような数のことです。
例として、24と32を考えます。最大公約数はいくつでしょうか。まず、両方の数を割り切る数を探します。
- たとえば12は24を割り切りますが、32は割り切りません。32 / 12 は2.666…で、整数ではないからです。したがって、12は24と32の最大公約数ではありません。
- 4はどうでしょうか。4は両方を割り切ります。24 / 4 は6、32 / 4 は8です。これで、4が最初の候補になります。両方を割り切る、もっと大きな数はないでしょうか。
- 8は24も32も割り切り、しかも4より大きい数です。
- 両方を割り切る数で、8より大きいものはありません。したがって、8が24と32の最大公約数です。
ユークリッドの互除法で最大公約数を求める
2つの数の最大公約数は、ユークリッドの互除法を使えば、かなり簡単に求められます。はじめに、最大公約数を求めたい2つの数 x と y があるとします。例として、x = 50、y = 35 で試してみましょう。次のように進めます。
- x / y を計算し、割り算の余りを覚えておきます。この余りを z とします。この例では 50 / 35 を計算し、余りは z = 15 です。
- 次に変数を入れかえます。変数 x に y の値を、y に z の値を入れます。x のもとの値は捨てます。この手順のあとは、x = 35、y = 15 です。
- ここで、y が0かどうかを調べます。0なら、x が最大公約数です。y は0ではないので、1にもどって、手順をくり返します。
- もう一度 x / y、つまり 35 / 15 を計算すると、割り算の余りは z = 5 です。
- 変数を入れかえると、x = 15、y = 5 になります。y は0ではないので、続けます。
- x / y、つまり 15 / 5 を計算します。割り算の余りは z = 0 です。
- 変数を入れかえると、x = 5、y = 0 になります。
- ここで y = 0 なので、手順は終わりです。最大公約数は x = 5 です。
なお、2つの数の順番はどちらでもかまいません。例の数を入れかえると、x = 35、y = 50 の組になります。手順は同じです。
- x / y、つまり 35 / 50 を計算すると、余りは z = 35 です。
- 変数を入れかえると、x = 50、y = 35 になります。
- ここまでで、変数 x と y の中身がたがいに入れかわっただけだとわかります…
計算ツール
この計算ツールで最大公約数を計算できます。