互いに素の判定計算

二つの整数の最大公約数がちょうど一のとき、それらは互いに素といいます。それぞれの数が素数である必要はありません。例えば 14 と 25 はどちらも合成数で、14 は因数 2 と 7、25 は因数 5 を持ちますが、1 以外に共通の正の因数はありません。一方、18 と 24 は因数 2、3、6 を共有するため、最大公約数は 6 で、互いに素ではありません。 この計算機はユークリッドの互除法で最大公約数を求めます。二つの整数の絶対値から始め、現在の数の組を除数と余りの組に繰り返し置き換えます。18 と 24 では、割り算の余りが最終的に 6、次に 0 になります。最後のゼロでない余りが最大公約数です。余りを取るたびに次の計算の数が急速に小さくなるため、大きな整数でも効率よく計算できます。 互いに素という性質は、単独の数ではなく数同士の関係です。整数 8 は 15 とは最大公約数が 1 なので互いに素ですが、12 とは因数 4 を共有するため互いに素ではありません。連続する整数は常に互いに素です。n と n に 1 を加えた数の公約数は、その差である 1 も割り切る必要があるためです。同様に、どの整数も 1 と互いに素です。 互いに素な数は約分の中心となる考え方です。分子と分母が互いに素であることと、分数が既約であることは同値です。合同算術、オイラーのトーシェント関数、周期的なパターン、歯車比、公開鍵暗号にも登場します。RSA 型の数学では、最大公約数が一となる値を選ぶことで、法に関する逆元の存在を保証できます。 符号は共通の正の因数を変えないため、負数も入力できます。最大公約数の計算には絶対値を使います。ゼロには注意が必要です。ゼロと非ゼロ整数の最大公約数はその整数の絶対値なので、ゼロと互いに素なのは 1 と負の 1 だけです。このツールではゼロ同士の最大公約数を通常の定義では定まらないものとして扱い、入力を受け付けません。互いに素や整除性は離散的な数論の概念なので、整数を入力してください。