久留島・オイラー関数 - Security Akademeia

目次 †

目次
久留島・オイラー関数
久留島・オイラー関数と既約剰余類系の関係
久留島・オイラー関数の性質
オイラーの定理
参考文献

↑

久留島・オイラー関数 †

[定義]正の整数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までの整数を長方形に並べる。

1	2	3	…	h	…	u
u+1	u+2	u+3	…	u+h	…	2u
2u+1	2u+2	2u+3	…	2u+h	…	3u
…	…	…	…	…	…	…
(v-1)u+1	(v-1)u+2	(v-1)u+3	…	(v-1)u+h	…	uv

このとき、各行が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]まず⇒を証明する。

　同様にして、(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_m$ 、 $x~\,~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=0	y=1	y=2	y=3	y=4
x=0	0	3	6	9	12
x=1	5	8	11	14	17
x=2	10	13	16	19	22

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

φ(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$ が成り立つ。　□