互いに素の数の計算機

互いに素な数とは、共通する正の約数が1だけである2つ以上の整数です。この計算機は、最大公約数（GCD）を求めて、入力した数が互いに素かどうかを判定します。GCDが1であれば、その数は互いに素です。

互いに素な数は、相対的に素な数、または相互に素な数とも呼ばれます。

互いに素とはどういう意味か？

2つの整数は、1より大きい整数で両方を割り切れるものがないとき、互いに素です。数自体が素数である必要はありません。たとえば、8と15は互いに素です。8の約数は1、2、4、8であり、15の約数は1、3、5、15です。共通する約数は1だけなので、これらは互いに素です。

これに対して、12と18は互いに素ではありません。どちらも2、3、6で割り切れるため、最大公約数は6です。

数が互いに素かどうかを調べる方法

すべての数の最大公約数（GCD）を求めます。GCDとは、すべての数を余りなく割り切れる最大の整数です。
GCDを1と比較します。GCDが1に等しければ、その数は互いに素です。GCDが1より大きければ、互いに素ではありません。

複数の数のGCDは、2つずつユークリッドの互除法を適用して求めます。3つの数a、b、cのGCDは、GCD(GCD(a, b), c)です。

互いに素の公式

数a₁、a₂、…、aₙが互いに素である条件は次のとおりです。

GCD(a₁, a₂, …, aₙ) = 1

計算例

6、10、15が互いに素かどうかを調べます。

GCD(6, 10) = 2
GCD(2, 15) = 1

3つすべての数の最大公約数は1なので、6、10、15は集合として互いに素です。

ただし、これら三つの数は、どの二つを選んでも互いに素というわけではありません。6と10は約数2を共有し、6と15は約数3を共有し、10と15は約数5を共有します。集合として互いに素であること（すべての数のGCDが1であること）は、どの二つを選んでも互いに素であること（すべての組のGCDが1であること）よりも弱い条件です。この計算機は両方を判定します。

どの二つを選んでも互いに素である場合と、集合として互いに素である場合の違い

数の集合全体のGCDが1であるとき、その集合は集合として互いに素です。集合内の考えられるすべての組のGCDが1であるとき、その集合はどの二つを選んでも互いに素です。どの二つを選んでも互いに素な数は常に集合として互いに素ですが、その逆は必ずしも成り立ちません。上の例がそのことを示しています。

よくある質問

1と任意の数は互いに素ですか？

はい。数1は、どの整数とも1より大きい約数を共有しないため、1は自身を含むすべての整数と互いに素です。

互いに素な数は素数でなければなりませんか？

いいえ。互いに素な数は合成数でもかまいません。8と15はどちらも合成数ですが、1以外に共通する約数がないため、互いに素です。

異なる二つの素数は必ず互いに素ですか？

はい。異なる2つの素数には1以外に共通する約数がないため、異なる2つの素数は必ず互いに素です。

負の数は互いに素になれますか？

互いに素であることは、通常、正の整数について定義されます。この計算機では、1以上の正の整数を扱います。

GCDと互いに素の違いは何ですか？

GCDとは、入力されたすべての数を割り切れる最大の数です。「互いに素」とは、そのGCDが1に等しいという特定のケースを指します。

互いに素の数の計算機