このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

久留島・オイラー関数

[定義]正の整数mに対して、久留島・オイラー関数\phiは次のように定義される。

\phi~(m)~:=~\sharp~\{~a~|~1~\le~a~\le~m~\wedge~GCD~\(~a,m~\)~=1~\}

 つまり、φ(m)=(1〜mのうちでmと互いに素な数の個数)である。

 または、次のように書き直すこともできる。

\phi~(m)~:=~\sharp~\{~a~|~0~\le~a~\le~m-1~\wedge~GCD~\(~a,m~\)~=1~\}

例:φ(6)=(1〜6のうち6と互いに素な数の個数)=2 ←1と5だけが6と素になる。 ◇

[補講]多くの数学書ではオイラー関数と呼ぶが、日本の和算家である久留島義広【くるしまよしひろ】はオイラーよりも前に発見していることがわかっており、今後は久留島・オイラー関数と呼ばれる場面が多くなると思われる。 ◇

久留島・オイラー関数と既約剰余類系の関係

[定理]mを法とする既約剰余系の元(既約剰余類)の個数は、久留島・オイラー関数φ(m)と一致する。即ち、次が成り立つ。

\phi~(m)~=~\sharp~\{~(Z/mZ)^*}

[証明]

\sharp~\{~Z/mZ~\}~=\sharp~\{~\forall~a|~a+mZ~\} ←(Z/mZ)の要素の数はm個

\sharp~\{~(Z/mZ)^*~\}~=~\sharp~\{~\forall~a|~a+mZ~\wedge~GCD(a,m)=1~\} ←(Z/mZ)^*の可逆元

 よって、久留島・オイラー関数の定義より、題意が成り立つ。 □

久留島・オイラー関数の性質

1に対する久留島・オイラー関数の値

[定理]\phi~(1)~=~1

[証明]\phi~(1)~=~\sharp~\{~a~|~1~\le~1~\le~m~\wedge~GCD~\(~a,1~\)~=1~\}

 1≦a≦1⇒a=1より、GCD(a,1)=GCD(1,1)となるのは1個だけ。 □

素数に対する久留島・オイラー関数の値

[定理]素数pに対して、次が成り立つ。
\phi~(p)~=~p-1

[証明]1〜pのうちでpと互いに素な数は1〜p-1までのすべての数である。つまり、p-1個ある。 □

[補講1]位数nの巡回群G=<a>に対して、Gの生成元になれる。Gの元の個数はφ(n)である。

[補講2]剰余環Znにおいて、可逆な元の個数はφ(n)である。

素数ベキに対する久留島・オイラー関数の値

[定理]p:素数、n:正整数とする。 aが素数ベキpnのときは、次が成り立つ。

\phi~(p^n)~=~p^n~-~p^{n-1}

ただし、n≧1とする。

[証明]p^nより小さい正の数はp^n~-1個ある。

 また、a=p^nと互いに素でない数はpの倍数であり、p^{n-1}~-1個ある。なぜならば、pnより小さいpの倍数はp,2p,\cdots,(p^{n-1}-1)pだから。

 よって、 φ(pn)
=(全体の個数)-(a=pnとならない数の個数)
=(pn-1)-(pn-1-1)
=pn-1(p-1) □

久留島・オイラー関数の乗法性

[定理]久留島・オイラー関数の直積分解(乗法性)
(a,b)=1~\Rightarrow~\phi(ab)=\phi(a)~\phi(b)

例1:

  • \phi(12)=~\sharp~\{~1,5,7,11~\}=4
  • \phi(4)=~\sharp~\{~1,3~\}=2
  • \phi(3)=~\sharp~\{~1,2~\}=2
  • \phi~(12)~=~\phi~(4)~\phi~(3)

例2:

  • u=9(列の数)
  • v=4(行の数)
  • uv=36

よって、

  • \phi(u)=6
  • \phi(v)=2
  • \phi(uv)=12

[証明]u,v:互いに素な正整数、m=uvとしたときに、\phi~(m)~=~\phi(uv)~=~\phi(u)~\phi(v)が成り立つことを調べる。

1からm=uvまでの整数を長方形に並べる。

123hu
u+1u+2u+3u+h2u
2u+12u+22u+32u+h3u
(v-1)u+1(v-1)u+2(v-1)u+3(v-1)u+huv

このとき、各行がuを法とする完全剰余系になっている。また各列がuを法とする合同類の一部になっている。

[1]ある1つの列(v行1列の行列)に出てくる2つの整数が、vを法として合同でないことを示す

\begin{bmatrix}h~\\~u+h~\\~2u+h~\\~\vdots~\\~(v-1)v+h~\end{bmatrix} ←(*)

から2つの数a=pu+h,b=qu+h(ここで、p,qはv-1以下の異なる正整数とする)と置く。

ここで、a~\equiv~b~\pmod{v}と仮定すると、

pu+h~\equiv~qu+h~\pmod{v}
u(p-q)~\equiv~0~\pmod{v}
p-q~\equiv~0~\pmod{v} (∵(u,v)=1)
p~\equiv~q~\pmod{v}

これはp,qは異なる正整数ということに矛盾。

よって、p~\not{\equiv}~q~\pmod{v}

 それぞれの列にはv個の数が並んでいて、そのうちどの2つの数もvを法として合同ではないことがわかったので、これらはvを法とする完全剰余系である。

 各列においてvと互いに素な整数は\phi~(v)個ある。これがどの列についても成り立つ。

[2](*)はuを法とする合同類の一部、即ちuを法とするAuであることを示す

これに含まれる数はすべてau+hの形の整数である(ただし、aは整数)。

[定理]「(u,v)=1 ⇒ (u,au+h)=1」より、この表のu個の列のうち、uと互いに素な数から成る列は\phi(u)個ある。そして、それらの列に出てくる数はすべてuと互いに素である。

 [1][2]より、uと互いに素な数から成る\phi(u)個の列それぞれが、vと互いに素な\phi(v)個の整数を含んでいる。

 よって、この表中のuv個の整数のうちに、uともvとも互いに素な整数は\phi(u)~\phi(v)個存在する。 □

[別証]n=ab,(a,b)=1

 A=~\{~ay+bx~|~x=0,1,\cdots,a-1~;~y=0,1,\cdots,b-1~\}はnを法とする剰余系である。 …

 なぜならば、A~\ni~ay+bx~,~ay'+bx'となり、ay+bx~\equiv~ay'+bx'~\,~(mod~\,~n)になる。以降次のように展開していく。

ay+bx~\equiv~ay'+bx'~\,(mod~\,~n)
a(y-y')~\equiv~b(x'-x)~\,(mod~\,~n)
a(y-y')~\equiv~0~\,(mod~\,~b)
y-y'~\equiv~0~\,(mod~\,~b) (∵「(a,b)=1∧a|bc」⇒「a|c」)
y=y'

同様にして、x=x'

 さらに、A~\ni~ay+bxに対して、次が成り立つ。

(ay+bx,n)=1~\Longleftrightarrow~(x,a)=1,(y,b)=1 …

[1]まず⇒を証明する。

 d=(x,a)とすると、d|ay+bxが成り立つ。また、a|nより、d|nが成り立つ。よって、d|(ay+bx,n)となり、展開するとd|1になり(∵仮定より)、最終的にd=1である。つまり、(x,a)=1になる。

 同様にして、(y,b)=1になる。

[2]次に←を証明する。

 (ay+bx,a)=(bx,a)=1(∵(x,a)=1)となる。同様にして、(ay+bx,b)=(ay,b)=1となる。n=abより、(ay+bx,n)=1になる。

 以上より、次のように計算できる。

\phi(n)
=~\sharp~\{~ay+bx~\in~A~|~(ay+bx,n)=1~\} (φの定義と ay+bxをブロックとして考える)
=~\sharp~\{~ay+bx~\in~A~|~(x,a)=1~\wedge~(y,b)=1~\} (∵△裏諭
=~\sharp~\{~ay+bx~\in~A~|~(ay+bx,a)=1~\wedge~(ay+bx,b)=1~\} (∵△裏)
=~\sharp~\{~ay+bx~\in~A~|~(ay+bx,a)=1~\}~\times~\sharp~\{~ay+bx~\in~A~|~(ay+bx,b)=1~\} (∵個数は直積分解できる)
=\phi(a)~\cdot~\phi(b) □

[別証]写像fを「f:~Z/(mn)~\rightarrow~Z/(m)~\times~Z/(n)」とする。fによるZmnの像がちょうどZm×Znであることを示せば、fが1対1であることによって証明が終わる。

 x~\,~mod~\,~mn~\in~Z_{mn}とすると、その定義から(x,mn)=1であり、(x,m)=(x,n)=1となる。よって、x~\,~mod~\,~m~\in~Z_mx~\,~mod~\,~n~\in~Z_nである。これで、f(Z_{mn})~\subset~Z_m~\times~Z_nが成り立つ。

 次に、(~x~\,~mod~\,~m~,~y~\,~mod~\,~n~)~\in~Z_m~\times~Z_n即ち、「x mod m∈Zm∧y mod n∈Zn」とする。中国人剰余定理より、「z≡x (mod m)∧z≡y (mod n)」を満たすz(∈Z)は存在する。
 「z≡x (mod m)∧(x,m)=1」によって、(z,m)=1となる。同様に(z,n)=1となる。よって、(z,mn)=1である。即ち、z mod mn∈Zmnである。
 さらに、f(~z~\,~mod~\,~mn~)=(~x~\,~mod~\,~m~,y~\,~mod~\,~n)なので、Z_m~\times~Z_n~\subset~f(Z_{mn})が成り立つ。

 以上から、f(Z_{mn})~=~Z_m~\times~Z_nが示された。 □

[別証]φ(mn)は位数mnの巡回群Gの元で、生成元になれるものの個数である。

 (m,n)=1より、この群Gは位数m,nの巡回群G1,G2の直積に分解される。

 部分群G1,G2で生成元になれる元の個数はそれぞれφ(m),φ(n)であるが、これらの元の積と巡回群Gの生成元になれる元は一致する。

 したがって、φ(mn)=φ(m)φ(n)が成り立つ。 □

例:a=3,b=5,n=ab=15

A={3y+5x|x=0,1,2;y=0,1,2,3,4}とすると、このときAがとりうる値すべてを表にすると次のようになる。

y=0y=1y=2y=3y=4
x=0036912
x=158111417
x=21013161922

 青い数の部分が既約剰余系の元になる。

φ(15)=φ(5)×φ(3)=4×2=8

合成数に対する久留島・オイラー関数の値

[定理]m1,…,mnが2つずつ互いに素となる正整数とし、m=m_1~m_2~\cdots~m_nとおく。このとき、次が成り立つ。

\phi~(m)=~\phi(m_1)\phi(m_2)\cdots\phi(m_n)

[証明](Z/mZ)^*~\simeq~(Z/m_{1}Z)^*~\times~(Z/m_{2}Z)^*~\times~\cdots~\times~(Z/m_{n}Z)^* □

[定理]正整数mの標準分解がm=p^a~\times~q^b~\times~r^cとする。
このとき、\phi(m)~=~m~(1-~\frac{1}{p})~(1-~\frac{1}{q})~(1-~\frac{1}{r})

[証明]

\phi(m)
=\phi(p^a~\times~q^b~\times~r^c)
=~(p^a~-~p^{a-1})~(q^b~-~q^{b-1})~(r^c~-~r^{c-1})
=~p^a(1~-~\frac{1}{p})~q^b(1~-~\frac{1}{q})~r^c(1~-~\frac{1}{r})
=~p^a~q^b~r^c~(1~-~\frac{1}{p})~(1~-~\frac{1}{q})~(1~-~\frac{1}{r})
=~m~(1-~\frac{1}{p})~(1-~\frac{1}{q})~(1-~\frac{1}{r}) □

 これは一般にも成り立つ。

[定理]mを正整数とし、m=p_1^{e_{1}}p_2^{e_{2}}\cdots~p_n^{e_{n}}をmの素因数分解とする。このとき、次が成り立つ。

\phi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})

[証明]\phi(m)
\phi(p_1^{e_{1}}p_2^{e_{2}}\cdots~p_n^{e_{n}})
=~\phi(p_1^{e_{1}})~\phi(p_2^{e_{2}})~\cdots~\phi(p_n^{e_{n}}) (∵上記の定理により)
=~p_1^{e_{1}-1}(p_1~-1)~p_2^{e_{2}-1}(p_2~-1)~\cdots~~p_m^{e_{m}-1}(p_m~-1)
=~p_1^{e_{1}}(1-\frac{1}{p_1})~~p_2^{e_{2}}(1-\frac{1}{p_2})~\cdots~p_n^{e_{n}}(1-\frac{1}{p_n})
=p_1^{e_{1}}p_2^{e_{2}}~\cdots~p_n^{e_{n}}(1-\frac{1}{p_1})~(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})
=m(1-\frac{1}{p_1})~(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n}) □

久留島・オイラー関数と和

[定理]mのすべての約数(1とmを含め)dについての和はmになる。即ち、次が成り立つ。

\sum_{~d|m,d~\ge~1}~\phi~(d)~=m

[証明]d|nとする。

\sharp~\{~x~|~1~\leq~x~\leq~m~\wedge~(x,m)=d~\}
=~\sharp~\{~x~|~1~\leq~x~\leq~m~\wedge~(~\frac{x}{d}~,\frac{m}{d}~)=1~\} (∵(x,m)=d~\Longleftrightarrow~(\frac{x}{d},frac{m}{d})=1
=\phi~(\frac{m}{d})

 一方、\{~1,2,~\cdots~,m~\}~=~\coprod_{d|m}~\{~x|1~\le~x~\le~m~\wedge~(x,m)=d~\}が成り立つ。よって、個数で考えると\sharp~\{~1,2,~\cdots~,m~\}~=~\sharp~\{~\coprod_{d|m}~\{~x|1~\le~x~\le~m~\wedge~(x,m)=d~\}~\}~=~\sharp~\{~x~|~1~\leq~x~\leq~m~\wedge~(x,m)=d~\}のように書き換えられる。

 以上より、題意が成り立つ。 □

[別証]本質的に上と同じ。

 d|mとするとき、1,…,mの中の数xで(x,m)=dとなるものの個数はφ(m/d)である。なぜならば、(x,m)=dのとき、x'=x/d,m'=m/dとおけば、「1≦x'≦m';(x',m')=1」だから、「1≦x≦m;(x,m)=d」となる。数xとx'(1≦x'≦m';(x',m')=1を満たす)とは、x'=x/dの関係によって1対1対応する。よって、x'の個数はφ(m')=φ(m/d)であるからである。

 nの約数の全体をd0,…,dnとするとき、任意のx(1≦x≦m)に対する(x,m)はd0,…,dnのどれかに等しい。よって、1,…,mは次のように分割される。

  • (x,m)=d0となるxの集合
  • (x,m)=d1となるxの集合
  • (x,m)=d2となるxの集合

 各集合の元の個数は、すでに見たように\phi(\frac{m}{d_0}),\cdots,\phi(\frac{m}{d_n})であるが、\frac{m}{d_0},\cdots,\frac{m}{d_n}に等しいから、\sum_{~d|m,d~\ge~1}~\phi~(d)~=mが成り立つ。 □

例1:m=6のときに、この定理が成り立つことを確認してみる。

(6の約数)={1,2,3,6}

(左辺)=φ(1)+φ(2)+φ(3)+φ(6)=1+1+2+2=6=(右辺)

例2:m=7のときに、この定理が成り立つことを確認してみる。

(7の約数)={1,7}

(左辺)=φ(1)+φ(7)=1+6=7=(右辺)

[考察]\sum_{~d|m,d~\ge~1}~\phi~(d)~=mとなる数論的関数*1φはオイラー関数のみである。

[考察]m:正整数
a_1,a_2,\cdots,a_l:mと互いに素なm以下の正整数を小さい順に並べた数列 ←(*)

とする。

(ここで、必ずa_1=1,l=\phi(m)が成り立つ)

上記の定理より、もし数列(*)の中に、ある整数aが現れるならば、m-aもこの中に現れるはずである。

この和はa+(m-1)=mとなる。

このような和がmである2つの整数から成る対の個数は、\frac{l}{2}=\frac{1}{2}\phi(m)個ある。

よって、

((*)の総和)
=~m~\times~\frac{1}{2}~\phi(m)
=~\frac{1}{2}~m~\phi(m)
=~\frac{1}{2}~m^2~(1-\frac{1}{p})~(1-\frac{1}{q})~(1-\frac{1}{r})~\cdots

例:m=9のとき

久留島・オイラー関数と合同類

[定理]mと互いに素な、m以下の正整数をr_1,r_2,~\cdots,~r_nとする(ただし、n=\phi(m))。
このとき、mを法とする合同類A_{r_1},~\cdots,~A_{r_n}に含まれる整数はすべてmと互いに素である。

例:m=9とする。

m(=9)と互いに素な、m(=9)以下の正整数は、1,2,4,5,7,8である(個数は\phi(9)=6個)。ここで、r_1=1,r_2=2,r_3=4,r_4=5,r_5=7,r_6=8とおく。

このとき各ri(1≦i≦6、i:整数)に対する合同類は次のようになる。

  • A_{r_1}=A_1=~\{~\cdots,~1,~10~,\cdots~\}
  • A_{r_2}=A_2=~\{~\cdots,~2,~11~,\cdots~\}
  • A_{r_3}=A_4=~\{~\cdots,~4,~13~,\cdots~\}
  • A_{r_4}=A_5=~\{~\cdots,~5,~14~,\cdots~\}
  • A_{r_5}=A_7=~\{~\cdots,~7,~16~,\cdots~\}
  • A_{r_6}=A_8=~\{~\cdots,~8,~17~,\cdots~\}

ここに登場する数値はすべてm(=9)と互いに素になっている。

[証明]r_1,r_2,\cdots,r_nのうち、任意の1つをrとする。

すると、仮定より(r,m)=1 ←(*)

また、集合Ar(合同類)に含まれる整数は、r+km~(k~\in~\mathbb{Z})と表される。

(m,r+km)~\not{=}~1と仮定する。

すると1以外の公約数dを持つため、r+km=da,m=dbとなる整数a,bが存在する。

このとき、

r+km=da
r+kdb=da (∵m=db)
r=d(a-kb)

ここでr=d(a-kb)かつm=dbより、(r,m)≠1

これは(*)に反する。

ゆえに、(m,r+km)~=~1 □

オイラーの定理

[定理]オイラーの定理(Euler's theorem)
mを正整数、aを整数とする。このとき、次が成り立つ。
「(a,n)=1」⇒「a^{\phi(n)}~\equiv~1~(~mod~\,~n)

[証明]Znにおいて、可逆な元の全体Gは乗法に関して群をなす。Gの位数|G|はφ(n)である。

 また、仮定より「(a,n)=1」であるから、a∈Gである。aの位数はGの位数の約数であるから、Gのおいて「a^{\phi(n)}~=~1」である。

 これは、「a^{\phi(n)}~\equiv~1~(~mod~\,~n)」を意味する。 □

参考文献

  • 暗号講座のプレゼン資料
  • ゼミノート
  • 『現代暗号の基礎数理』


*1 自然数から自然数への写像となる関数