互いに素 (整数論)

互いに素な整数についての解説

互いに素、英語でいうところの "coprime" とは、二つの整数 a と b の最大公約数が 1 である状態を指します。これが意味することは、a と b を同時に割り切る正の整数が 1 だけであるということです。互いに素であることは、記号で表すと a ⊥ b とも書かれます。なお、英語で "coprime" の他に "disjoint" という単語も使われますが、ここでは整数に特有の意味として理解されます。

互いに素の具体例

例えば、3 と 10 の場合、共に割り切れる正の整数は 1 のみなので、これらは互いに素です。一方、3 と 6 では共通の因数が 3 であるため、互いに素ではありません。さらに具体的に729 と 1000 について考えると、これらも互いに素です。逆に729 と 1296 は、共通の因数として 3、9、27、81の四つを持つため、互いに素とは言えません。1000 と 1296 も同様で、2、4、8のような共通の約数が見つかります。

判定方法

互いに素かどうかの判定方法には、素因数分解を用いる方法がありますが、特に一方の整数が非常に大きい場合にはこの手法が困難になります。そこで、ユークリッドの互除法を使用して最大公約数を求める方が、一般的には遥かに早く正確な結果が得られます。正の整数n と互いに素な (1 から n の範囲内の) 整数の個数は、オイラー関数 φ(n) を使用して求めることができます。

三つ以上の整数

もし三つの整数 a, b, c が互いに素であるならば、gcd(a, b, c) = 1 となります。また、各ペアの最大公約数、つまり gcd(a, b)、gcd(b, c)、gcd(c, a) のすべてが1である時、これらを "対ごとに素" と呼びます。ただし、互いに素であるからといって必ずしも対ごとに素であるとは限らない点には注意が必要です。

性質

互いに素の整数にはいくつかの興味深い性質があります。たとえば 0 と互いに素となる整数は 1 および -1 のみです。また、任意の整数も 1 および -1 とは互いに素です。異なる二つの素数は常に互いに素であり、隣接する整数も同じく互いに素です。さらに、もし a と b1 が互いに素であり、a と b2 も互いに素である場合、a と b1b2 も互いに素です。

また、互いに素であることと等価な条件がいくつか挙げられます。

1. a, b を共に割り切る素数が存在しないこと。
2. ax + by = 1 を満たす整数 x, y が存在すること （これはベズーの等式とも関連しています）。
3. b が a を法とする逆数を持つこと。
4. a, b の最小公倍数 lcm(a, b) が積 ab に等しいこと。
5. a, b の最大公約数 gcd(a, b) が 1 であること。
6. 2a − 1 と 2b − 1 が互いに素であること。

確率論的アプローチ

任意に選んだ二つの整数 a と b が互いに素である確率は、一つの素数 p に対して、少なくとも一方が p の倍数でないことに基づいて計算できます。全ての p に対してこれを行い、独立な試行として扱うことで確率を求められます。この計算の結果、互いに素である確率はおおよそ 0.6079271 となります。この値はリーマンのゼータ関数を用いた結果であり、一般的に任意に選んだ k 個の整数が互いに素である確率は 1/ζ(k) で表現されます。

互いに素の生成法

すべての互いに素な正の整数の組 (m, n)（m > n）は、二つの完全三分木を用いることで生成できます。一つは (2, 1) から偶数と奇数の組を、もう一つは (3, 1) から奇数・奇数の組を生成します。このプロセスで生成されるすべての組は互いに素であり、重複がありません。

結論

互いに素の概念は、数論の中で非常に重要な役割を果たします。数学だけでなく、実生活の中でもそれに基づく応用が多々存在します。たとえば、固定ギアの自転車の設計において、チェーンリングとコグの歯数が互いに素であれば、スキッドポイントが特定されやすくなります。

もう一度検索