[定義]正の整数mに対して、久留島・オイラー関数は次のように定義される。
つまり、φ(m)=(1〜mのうちでmと互いに素な数の個数)である。
または、次のように書き直すこともできる。
例:φ(6)=(1〜6のうち6と互いに素な数の個数)=2 ←1と5だけが6と素になる。 ◇
[補講]多くの数学書ではオイラー関数と呼ぶが、日本の和算家である久留島義広【くるしまよしひろ】はオイラーよりも前に発見していることがわかっており、今後は久留島・オイラー関数と呼ばれる場面が多くなると思われる。 ◇
[定理]mを法とする既約剰余系の元(既約剰余類)の個数は、久留島・オイラー関数φ(m)と一致する。即ち、次が成り立つ。
[証明]
←
の要素の数はm個
←
の可逆元
よって、久留島・オイラー関数の定義より、題意が成り立つ。 □
[定理]
[証明]
1≦a≦1⇒a=1より、GCD(a,1)=GCD(1,1)となるのは1個だけ。 □
[定理]素数pに対して、次が成り立つ。
[証明]1〜pのうちでpと互いに素な数は1〜p-1までのすべての数である。つまり、p-1個ある。 □
[補講1]位数nの巡回群G=<a>に対して、Gの生成元になれる。Gの元の個数はφ(n)である。
[補講2]剰余環Znにおいて、可逆な元の個数はφ(n)である。
[定理]p:素数、n:正整数とする。 aが素数ベキpnのときは、次が成り立つ。
ただし、n≧1とする。
[証明]より小さい正の数は
個ある。
また、と互いに素でない数はpの倍数であり、
個ある。なぜならば、pnより小さいpの倍数は
だから。
よって、
φ(pn)
=(全体の個数)-(a=pnとならない数の個数)
=(pn-1)-(pn-1-1)
=pn-1(p-1) □
[定理]久留島・オイラー関数の直積分解(乗法性)
例1:
例2:
よって、
[証明]u,v:互いに素な正整数、m=uvとしたときに、が成り立つことを調べる。
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を法として合同でないことを示す
列 ←(*)
から2つの数a=pu+h,b=qu+h(ここで、p,qはv-1以下の異なる正整数とする)と置く。
ここで、と仮定すると、
(∵(u,v)=1)
これはp,qは異なる正整数ということに矛盾。
よって、
それぞれの列にはv個の数が並んでいて、そのうちどの2つの数もvを法として合同ではないことがわかったので、これらはvを法とする完全剰余系である。
各列においてvと互いに素な整数は個ある。これがどの列についても成り立つ。
[2](*)はuを法とする合同類の一部、即ちuを法とするAuであることを示す
これに含まれる数はすべてau+hの形の整数である(ただし、aは整数)。
[定理]「(u,v)=1 ⇒ (u,au+h)=1」より、この表のu個の列のうち、uと互いに素な数から成る列は個ある。そして、それらの列に出てくる数はすべてuと互いに素である。
[1][2]より、uと互いに素な数から成る個の列それぞれが、vと互いに素な
個の整数を含んでいる。
よって、この表中のuv個の整数のうちに、uともvとも互いに素な整数は個存在する。 □
[別証]n=ab,(a,b)=1
はnを法とする剰余系である。 …
なぜならば、となり、
になる。以降次のように展開していく。
(∵「(a,b)=1∧a|bc」⇒「a|c」)
同様にして、
さらに、に対して、次が成り立つ。
…
[1]まず⇒を証明する。
d=(x,a)とすると、が成り立つ。また、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になる。
以上より、次のように計算できる。
(φの定義と ay+bxをブロックとして考える)
(∵△裏諭
(∵△裏)
(∵個数は直積分解できる)
□
[別証]写像fを「」とする。fによるZmnの像がちょうどZm×Znであることを示せば、fが1対1であることによって証明が終わる。
とすると、その定義から(x,mn)=1であり、(x,m)=(x,n)=1となる。よって、
、
である。これで、
が成り立つ。
次に、即ち、「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である。
さらに、なので、
が成り立つ。
以上から、が示された。 □
[別証]φ(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を正整数とし、をmの素因数分解とする。このとき、次が成り立つ。
[証明]
(∵上記の定理により)
□
[定理]mのすべての約数(1とmを含め)dについての和はmになる。即ち、次が成り立つ。
[証明]d|nとする。
(∵
)
一方、が成り立つ。よって、個数で考えると
のように書き換えられる。
以上より、題意が成り立つ。 □
[別証]本質的に上と同じ。
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は次のように分割される。
各集合の元の個数は、すでに見たようにであるが、
に等しいから、
が成り立つ。 □
例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=(右辺)
[考察]となる数論的関数*1φはオイラー関数のみである。
[考察]m:正整数
:mと互いに素なm以下の正整数を小さい順に並べた数列 ←(*)
とする。
(ここで、必ずが成り立つ)
上記の定理より、もし数列(*)の中に、ある整数aが現れるならば、m-aもこの中に現れるはずである。
この和はa+(m-1)=mとなる。
このような和がmである2つの整数から成る対の個数は、個ある。
よって、
((*)の総和)
例:m=9のとき
[定理]mと互いに素な、m以下の正整数をとする(ただし、
)。
このとき、mを法とする合同類に含まれる整数はすべてmと互いに素である。
例:m=9とする。
m(=9)と互いに素な、m(=9)以下の正整数は、1,2,4,5,7,8である(個数は個)。ここで、
とおく。
このとき各ri(1≦i≦6、i:整数)に対する合同類は次のようになる。
ここに登場する数値はすべてm(=9)と互いに素になっている。
[証明]のうち、任意の1つをrとする。
すると、仮定より(r,m)=1 ←(*)
また、集合Ar(合同類)に含まれる整数は、と表される。
と仮定する。
すると1以外の公約数dを持つため、となる整数a,bが存在する。
このとき、
(∵m=db)
ここでr=d(a-kb)かつm=dbより、(r,m)≠1
これは(*)に反する。
ゆえに、 □
[定理]オイラーの定理(Euler's theorem)
mを正整数、aを整数とする。このとき、次が成り立つ。
「(a,n)=1」⇒「」
[証明]Znにおいて、可逆な元の全体Gは乗法に関して群をなす。Gの位数|G|はφ(n)である。
また、仮定より「(a,n)=1」であるから、a∈Gである。aの位数はGの位数の約数であるから、Gのおいて「」である。
これは、「」を意味する。 □