互いに素

互いに素(coprime)とは、与えられた2つの整数が共通の素因数を持たないことを意味します。
例えば、4と6なら、

4 = 22
6 = 2•3

だから、2が共通の素因数となり、互いに素ではありません。12と25なら、

12 = 22•3
25 = 52

だから、互いに素です。
プログラムでこれを調べたいときは、最大公約数が1かどうかを調べます。1なら互いに素、そうでなければ互いに素でないことになります(負数を扱うときは注意)。


互いに素は、Project Eulerを解いていても意外とよく出てくる概念です。例えば、辺の長さがa, b, cの三角形を考えるとき、これらが互いに素でなければ、最大公約数で割った辺の長さの三角形と相似なので、こちらだけ考えればよい、などというように使われます。


関連
ユークリッドの互除法