ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


オイラーのφ関数


ヨミ: オイラーノファイカンスウ
掲示板をミル!
4カキコ!

オイラーφ(ファイ)関数、またはオイラーのトーシェント関数とは、数論的関数の一つである。


概要


φ関数は、正の整数 n を引数に与えたときに、1 から n までの整数のうち n と互いに素(1を除く共通の約数を持たない)なものの個数を返す。




性質


おこφ関数を用いたものに、以下のオイラー定理がある。


オイラーの定理


nが正の整数でaをnと互いに素な正の整数としたとき、

   aφ(n) 1 mod n

が成立する。

オイラー定理で n = p (p は素数)とした場合がフェルマーの小定理である。

証明

1から n までの整数で n と互いに素な整数集合を A = {r1, r2, …, rφ(n)}とする。

ari (1≦i≦φ(n)) と n は互いに素、かつ i ≠ j なら ariarj mod n なので、Aの各要素に a を乗じた集合B = {ar1, ar2, …, arφ(n)} はnを法としたときAと一致する。・・・(2)

P = r1・r2・…・rφ(n)とすると、(2)より P aφ(n)P mod n

n と P は互いに素だから、合同式の基本性質から、両辺に P の逆元を乗じて、aφ(n) 1 mod n.  ■


群論への応用


自然数nに対し、上記の合同を同値関係として同値類を取り、n>1として1以上n以下のnと素な自然数の同値類の集合を考えると、整数の乗法と剰余を取る操作を演算としてを成す。

要するに余り同士に対しある種の演算を導入すると「」と呼ばれる構造を得る、ということである。

nで割った余りがmである整数集合を[m]と表す。例えばnが2の時は[0]は偶数集合、[1]は奇数集合である。

mを[m]の代表元という。代表元の選び方は1通りではなく、定義から 
   ...=[m-n]=[m]=[m+n]=[m+2n]=...
が成り立つことに注意。

集合 A={[a]|aはnと互いに素} を考える。このとき以下が成り立つ。

  1. Aの2つの元[a], [b] の積 [a][b] を
       [a][b] = [ab]
    で定めると、これはwell-defined である。つまり、上式の右辺の値は左辺の代表元 a, b のとり方に依らずに1通りに定まる。
  2. 1で定めた[a][b]は再びAの元になる。
  3. 結合法則 ([a][b])[c] = [a]([b][c]) が成り立つ。
  4. Aは単位元として[1]を持つ。
  5. Aの任意の元は逆元を持つ。

証明


1. は [a]=[a'], [b]=[b'] を満たす代表元 a', b' を用意しても [ab]=[a' b'] が成り立つことを示せば良い。定義から a-a' と b-b' は nの倍数なので、ある整数 k, l を用いて a-a'=kn, b-b'=ln と表せる。このとき、ab-a'b' = (a'+kn)(b'+ln)-a'b' = (kb'+la'+kl)n なので ab-a'b' はnの倍数。よって[ab]=[a' b'] が成り立つ。■

2. を示す。aとnは互いに素、かつbとnは互いに素なので、aはnと共通の素因数を持たないし、bもnと共通の素因数を持たない。ゆえに ab もnと共通の素因数を持たない。よって ab は n と互いに素だから、[ab] は A の元である。■

3., 4. は積の定義から明らか。■

5. を示す。[a]に対し、nはaと互いに素なのでax+ny=1を満たす整数x,yが存在する。このとき積の定義から [a][x]=[ax]=[1-ny]=[1] であるので、[a]の逆元[x]が存在する。■

以上 3., 4., 5. からAは群の要件を満たすことが確認できる。この群は「nと素な剰余類の成す乗法群」などと呼ばれ、 (Z/n)* や Zn* などと書く。

(Z/n)*は位数(群の要素の数)がφ(n)の有限可換群となる。特にnが素数ならば、位数n-1の巡回群となる。


具体例



関連項目



最終更新日: 19/07/30 01:52
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ