Mixing
互いに素
 |
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（2016年6月） |
二つの整数 a, b が互いに素（たがいにそ、英: coprime, co-prime, relatively prime, mutually prime）であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b の最大公約数 gcd(a, b) が 1 であることと同値である。a, b が互いに素であることを、記号で a ⊥ b と表すこともある[1]。
例えば 14 と 15 を共に割り切る正の整数は 1 に限られるから、これらは互いに素である。一方で 14 と 21 は共に 7 で割り切れるから、これらは互いに素でない。
互いに素であることの判定は素因数分解を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、ユークリッドの互除法によって最大公約数を調べる方法のほうが遥かに高速である。
正の整数 n と互いに素となる（1 から n の間の）整数の個数は、オイラー関数 φ(n) によって与えられる。
三つの整数 a, b, c が互いに素であるとは、gcd(a, b, c) = 1 が成り立つことをいう。また、gcd(a, b)、gcd(b, c)、gcd(c, a) がすべて 1 に等しいとき、a, b, c は対ごとに素（英: pairwise coprime）またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない（例：a = 6, b = 15, c = 10）。一般の n 個の整数についても同様に定義される。
目次
1 性質
2 互いに素である確率
3 互いに素な整数の組の生成
4 脚注
5 関連項目
性質
0 と互いに素となる整数は 1 と −1 だけであり、また任意の整数と互いに素となる整数も 1 と −1 だけである。- 異なる二つの素数は互いに素であり、連続する二つの整数も互いに素である。
2 以上の整数は、その（自身を含む）倍数や 2 以上の約数と互いに素でない。
a と b1、a と b2 がそれぞれ互いに素ならば、a と b1b2 も互いに素である。
以下は、整数 a, b が互いに素であることと同値な条件である。
a, b を共に割り切る素数が存在しない。
ax + by = 1 を満たす整数 x, y が存在する。（ベズーの等式を参照）
b は a を法とする逆数をもつ。即ち by ≡ 1 (mod a) を満たす整数 y が存在する。別の言い方をすれば、b は a を法とする剰余類環 Z/aZ の単元となっている。
a, b の最小公倍数 lcm(a, b) が積 ab に等しい。
a, b の最大公約数 gcd(a, b) が 1 に等しい。
2a − 1 と 2b − 1 が互いに素。
互いに素である確率
整数の中から任意に選んだ2つの数 a と b が互いに素である確率を、ナイーブには、以下のように求めることができる。
a と b が互いに素とは、任意の素数 p に対して、a と b の少なくとも一方が p の倍数でないこと、と言い換える。
p を固定したとき、この事象は、a, b がともに p の倍数である事象の余事象である。
a が p の倍数である確率は 1/p である。（b についても同様）
各 p に対して、これらの試行は独立だから、求める確率は、
- ∏p: prime{1−(1p)2}=(∏p: prime11−p−2)−1=1ζ(2)=6π2≈0.6079271.{displaystyle prod _{p:{text{ prime}}}left{1-left({frac {1}{p}}right)^{2}right}=left(prod _{p:{text{ prime}}}{frac {1}{1-p^{-2}}}right)^{-1}={frac {1}{zeta (2)}}={frac {6}{pi ^{2}}}approx 0.6079271.}
ここで、ζ はリーマンのゼータ関数を表す。ζ(2) の値はレオンハルト・オイラーによって求められた。一般に、任意に選んだ k 個の整数が互いに素である確率は 1/ζ(k) で表される。
互いに素な整数の組の生成
このアルゴリズムによる互いに素な組の生成の順番。最初のノード (2, 1) を赤、その三つの子ノードを橙、さらにその子ノードを黄色で示し、それ以降を虹色の順に色を用いて示した。
すべての互いに素な正の整数の組 (m, n)（ただし m > n）は、二つの互いに素な完全三分木を用いて並べることができる。片方の木は (2, 1) から始まり偶数・奇数および奇数・偶数の組を[2]、もう片方は (3, 1) から始まり奇数・奇数の組を[3]生成する。このときノード (m, n) から生成される三つの子ノードはそれぞれ次のように表される。
- (2m − n, m)
- (2m + n, m)
- (m + 2n, n)
以上により生成される組は常に互いに素であり、すべての組が重複なく網羅される。
脚注
^ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley
^ Saunders, Robert & Randall, Trevor (July 1994), “The family tree of the Pythagorean triplets revisited”, Mathematical Gazette 78: 190–193, doi:10.2307/3618576 .
^ Mitchell, Douglas W. (July 2001), “An alternative characterisation of all primitive Pythagorean triples”, Mathematical Gazette 85: 273–275, doi:10.2307/3622017 .
関連項目
- 最大公約数
- 素因数分解
- オイラーのφ関数
- 算術の基本定理
- 既約分数
