2016年6月24日 (金) 05:13時点における版編集新規作成 (会話 \| 投稿記録) 17,390 回編集 m編集の要約なし ← 古い編集		2016年6月28日 (火) 11:06時点における版編集取り消し Flightbridge (会話 \| 投稿記録) 拡張承認された利用者 1,082 回編集 en:Coprime integers oldid=724471964 より内容を追加、整理新しい編集 →
1行目: {{Otheruses\|2つの整数の関係\|互いに素な集合\|素集合}} {{出典の明記\|date=2016年6月}} 二つの[[整数]] {{math\|{{mvar\|a}}, {{mvar\|b}}}} が'''互いに素'''（たがいにそ、{{lang-en-short\|coprime, co-prime, relatively prime, mutually prime}}）であるとは、2つ{{math\|{{mvar\|a}}, {{mvar\|b}}}} を共に割り切る正の[[整数]]が ~~[[1]] と [[-1~~{{math\|~~−~~1]]}} ~~以外に[[公約数]]を持たない場合の2数~~の関係みであることをいう。これのことは~~2つの整数~~ {{math\|{{mvar\|a}}, {{mvar\|b}}}} の[[最大公約数]] {{math\|gcd({{mvar\|a}}, {{mvar\|b}})}} が {{math\|1}} であることと[[同値]]である。~~2つの整数 ''~~{{math\|{{mvar\|a''}}, ''{{mvar\|b''}}}} が互いに素であることを、記号で ''{{math\|{{mvar\|a''}} ⊥ ''{{mvar\|b''}}}} と表すこともある<ref>{{citation\|first1=R. L.\|last1=Graham\|first2=D. E.\|last2=Knuth\|first3=O.\|last3=Patashnik\|title=Concrete Mathematics\|publisher=Addison-Wesley\|year=1989}}</ref>。 3つの整数 ''a'', ''b'', ''c'' について、''a''　と ''b''、''b'' と ''c''、''c'' と ''a'' の公約数がそれぞれ 1 と −1 のみでなくても、''a'', ''b'', ''c'' の公約数としては 1 と −1 のみのときがある（例：''a'' = 6, ''b'' =15, ''c'' = 10）。このようなとき、''a'', ''b'', ''c'' は互いに素という。一般の''n''個の整数についても同様に定義される。例えば {{math\|14}} と {{math\|15}} を共に割り切る正の整数は {{math\|1}} に限られるから、これらは互いに素である。一方で {{math\|14}} と {{math\|21}} は共に {{math\|7}} で割り切れるから、これらは互いに素でない。 2整数の少なくとも1つが大きい場合、互いに素であるかどうかを知るのに、[[素因数分解]]による方法では、一般には困難である。[[素因数分解]]をせずに最大公約数を求める最良の[[アルゴリズム]]である、[[ユークリッドの互除法]]がある。これにより、最大公約数が 1 であれば互いに素、2 以上ならば互いに素ではないことが分かる。互いに素であることの判定は[[素因数分解]]を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、[[ユークリッドの互除法]]によって最大公約数を調べる方法のほうが遥かに高速である。 == 例 ==▼ 12 = 2{{sup\|2}} × 3 と 35 = 5 × 7 は、共通の[[素因数]]を持たないから公約数は 1 と分かる。したがって、互いに素である。6 = 2 × 3 と 14 = 2 × 7 は、2 を公約数に持つので、互いに素ではない。正の整数 {{mvar\|n}} と互いに素となる（{{math\|1}} から {{mvar\|n}} の間の）整数の個数は、[[オイラー関数]] {{math\|{{mvar\|φ}}({{mvar\|n}})}} によって与えられる。 1, −1 はそれぞれ（[[0]] や ±1 自身を含む）全ての整数と互いに素であり、0 は 1 および −1 とのみ互いに素である。一般に、異なる2つの[[素数]]は互いに素であり、連続する2つの整数も互いに素である。2 以上の整数は、その（自身を含む）[[倍数]]や 2 以上の約数と互いに素でない。三つの整数 {{math\|{{mvar\|a}}, {{mvar\|b}}, {{mvar\|c}}}} が'''互いに素'''であるとは、{{math\|gcd({{mvar\|a}}, {{mvar\|b}}, {{mvar\|c}}) {{=}} 1}} が成り立つことをいう。また、{{math\|gcd({{mvar\|a}}, {{mvar\|b}})}}、{{math\|gcd({{mvar\|b}}, {{mvar\|c}})}}、{{math\|gcd({{mvar\|c}}, {{mvar\|a}})}} がすべて {{math\|1}} に等しいとき、{{math\|{{mvar\|a}}, {{mvar\|b}}, {{mvar\|c}}}} は'''対ごとに素'''（{{lang-en-short\|pairwise coprime}}）または'''どの二つも互いに素'''であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない（例：{{math\|{{mvar\|a}} {{=}} 6, {{mvar\|b}} {{=}} 15, {{mvar\|c}} {{=}} 10}}）。一般の {{mvar\|n}} 個の整数についても同様に定義される。 == 互いに素である数の性質 ==▼ 整数 ''a'', ''b'' が互いに素ならば、''ax'' + ''by'' = 1 を満たす整数 ''x'', ''y'' が存在する。（証明は、ユークリッドの互除法による。） ''a'' と ''b''{{sub\|1}}、''a'' と ''b''{{sub\|2}} がそれぞれ互いに素ならば、''a'' と ''b''{{sub\|1}}''b''{{sub\|2}} も互いに素である。▼ ''a'' と ''b'' が互いに素であることと 2{{sup\|''a''}} − 1 と 2{{sup\|''b''}} − 1 が互いに素であることは[[同値]]である。 ▲== 例性質 == ~~=== 互いに素である確率 ===~~ {{math\|0}} と互いに素となる整数は {{math\|1}} と {{math\|−1}} だけであり、また任意の整数と互いに素となる整数も {{math\|1}} と {{math\|−1}} だけである。整数の中から任意に選んだ2つの数 ''a'' と ''b'' が互いに素である[[確率]]を、ナイーブには、以下のように求めることができる。▼ * 異なる二つの[[素数]]は互いに素であり、連続する二つの整数も互いに素である。 * {{math\|2}} 以上の整数は、その（自身を含む）[[倍数]]や {{math\|2}} 以上の約数と互いに素でない。 ▲'' {{mvar\|a''}} と ''{{math\|{{mvar\|b''}}{{~~sub~~msub\|1}}}}、''{{mvar\|a''}} と ''{{math\|{{mvar\|b''}}{{~~sub~~msub\|2}}}} がそれぞれ互いに素ならば、''{{mvar\|a''}} と ''{{math\|{{mvar\|b''}}{{~~sub~~msub\|1}}''{{mvar\|b''}}{{~~sub~~msub\|2}}}} も互いに素である。以下は、整数 {{math\|{{mvar\|a}}, {{mvar\|b}}}} が互いに素であることと同値な条件である。 ''a'' と ''b'' が互いに素とは、任意の[[素数]] ''p'' に対して、''a'' と ''b'' の少なくとも一方が ''p'' の倍数でないこと、と言い換える。▼ {{math\|{{mvar\|a}}, {{mvar\|b}}}} を共に割り切る[[素数]]が存在しない。 ''p'' を固定したとき、この[[事象]]は、''a'', ''b'' がともに ''p'' の倍数である事象の余事象である。▼ * {{math\|{{mvar\|ax}} + {{mvar\|by}} {{=}} 1}} を満たす整数 {{math\|{{mvar\|x}}, {{mvar\|y}}}} が存在する。（[[ベズーの等式]]を参照） * {{mvar\|b}} は {{mvar\|a}} を[[モジュラ逆数\|法とする逆数]]をもつ。即ち {{math\|{{mvar\|by}} ≡ 1 (mod {{mvar\|a}})}} を満たす整数 {{mvar\|y}} が存在する。別の言い方をすれば、{{mvar\|b}} は {{mvar\|a}} を法とする[[剰余類環]] {{math\|'''Z'''/{{mvar\|a}}'''Z'''}} の[[可逆元\|単元]]となっている。 * {{math\|{{mvar\|a}}, {{mvar\|b}}}} の[[最小公倍数]] {{math\|lcm({{mvar\|a}}, {{mvar\|b}})}} が積 {{mvar\|ab}} に等しい。 * {{math\|{{mvar\|a}}, {{mvar\|b}}}} の[[最大公約数]] {{math\|gcd({{mvar\|a}}, {{mvar\|b}})}} が {{math\|1}} に等しい。 * {{math\|2{{msup\|{{mvar\|a}}}} − 1}} と {{math\|2{{msup\|{{mvar\|b}}}} − 1}} が互いに素。 ▲== 互いに素である~~数の性質~~確率 == ''a'' が ''p'' の倍数である確率は {{sfrac\|1\|''p''}} である。（''b'' についても同様）▼ ▲整数の中から任意に選んだ2つの数 ''{{mvar\|a''}} と ''{{mvar\|b''}} が互いに素である[[確率]]を、ナイーブには、以下のように求めることができる。 ▲''{{mvar\|a''}} と ''{{mvar\|b''}} が互いに素とは、任意の[[素数]] ''{{mvar\|p''}} に対して、''{{mvar\|a''}} と ''{{mvar\|b''}} の少なくとも一方が ''{{mvar\|p''}} の倍数でないこと、と言い換える。 ▲''{{mvar\|p''}} を固定したとき、この[[事象]]は、''{{math\|{{mvar\|a''}}, ''{{mvar\|b''}}}} がともに ''{{mvar\|p''}} の倍数である事象の余事象である。 ▲''{{mvar\|a''}} が ''{{mvar\|p''}} の倍数である確率は {{math\|{{sfrac\|1\|''{{mvar\|p''}}}}}} である。（''{{mvar\|b''}} についても同様）各 ''{{mvar\|p''}} に対して、これらの試行は[[確率論的独立性\|独立]]だから、求める確率は、▼ ▲各 ''p'' に対して、これらの試行は[[確率論的独立性\|独立]]だから、求める確率は、 :<math>\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} 31 ⟶ 42行目: =\frac{6}{\pi^2} \approx 0.6079271.</math> ここで、{{mvar\|[[ζ]]}} は[[リーマンゼータ函数\|リーマンのゼータ関数]]を表す。[[バーゼル問題\|{{math\|''{{mvar\|ζ''}}(2)}} の値]]は[[レオンハルト・オイラー]]によって求められた。一般に、任意に選んだ {{mvar\|k}} 個の整数が互いに素である確率は {{math\|1/~~''ζ''~~{{mvar\|ζ}}(''{{mvar\|k''}})}} で表される。 == 脚注 == {{reflist}} == 関連項目 ==

「互いに素 (整数論)」の版間の差分