ファイ関数-φ(n) | n以下の自然数でnと互いに素なものの個数
ファイ関数 φ(n) （トーシェント関数）は、1 以上 n 以下の自然数の中で、n との最大公約数が 1 である自然数の個数を表しています。
このブログ記事では、前半で、高校数学の範囲でファイ関数の基本的な性質を解説しています。
後半では、剰余環 Z/nZ の乗法逆元が何個あるかという大学数学の内容を述べています。
自然数 a と b の最大公約数が 1 のとき、
φ(ab) = φ(a)φ(b) となるというファイ関数の乗法性は、中国剰余定理と入門的な群論からすぐに導かれます。
この記事で、自然数（1 以上の整数) a と b について、a の正の約数であり、なおかつ b の正の約数であるものを a と b の公約数と呼んでいます。
そして、a と b の公約数のなかで、通常の大小関係について最大のものを a と b の最大公約数と呼びます。
ファイ関数-φ :まずはφ(n)の定義から
【定義】
自然数 n に対して、1 以上 n 以下の自然数で、n との最大公約数が 1 である自然数の個数を φ(n) と表します。
定義から、自然数 1 に対して、φ(1) = 1 ということが分かります。1 以上 1 以下の自然数は 1 しかなく、1 と 1 との最大公約数が 1 だからです。
次に、素数について、ファイ関数のとる値を考えてみます。
nが素数のとき
素数 p について、φ(p) の値を考えます。p と p の最大公約数は p です。
素数は 2 以上の自然数なので、p と p の最大公約数は 1 ではありません。
残りの 1 以上 p － 1 以下の範囲の自然数を考えます。
素数の定義から、2 以上 p － 1 以下の自然数は p の約数ではありません。
そのため、k を 2 以上 p － 1 以下の自然数とすると、k と p の最大公約数は 1 です。そして、1 と p の最大公約数は 1 です。
よって、1 以上 p － 1 以下の自然数は、すべて p との最大公約数が 1 となっています。
ゆえに、φ(p) = p － 1
素数 p に対して、1 以上 p － 1 以下の自然数はすべて p との最大公約数が 1 なので、これら p － 1 個の自然数の個数が、φ(p) のとる値ということになります。
今度は、n が素数のベキ乗のときについて、
n と最大公約数が 1 となっている自然数が何個あるのかを数えてみます。
ここから、新しい記号を使うことにします。
整数 a が整数 b の約数であるときに、
a | b と表します。
※ a | b は b が a の倍数ということでもあります。
nが素数のベキ乗のとき
p を素数とし、k を自然数とします。
このとき、φ(pk) が何かを考えます。
1 以上 pk 以下の自然数 m と pk の 2 以上の 公約数を d とすると、d | pk です。
そのため、d を素因数分解したときに、p ではない素数を素因子としてもっていないことになります。
d は 2 以上で 1 ではないため、素因子として素数 p をもちます。
すなわち、
d = ps (s は自然数で 1 ≦ s ≦ k) です。
そして、d | m ですから m = d × t (t は整数) という形です。
d = ps なので、m = ps × t となり、m は p の倍数です。
つまり、1 以上 pk 以下の pk 個の自然数について、pk との最大公約数が 2 以上となっている自然数を素因数分解をすると、必ず p が素因子として現れます。
1 以上 pk 以下の範囲で、p で割り切れる自然数を書き出します。
言い方を換えると、1 以上 pk 以下の範囲にある p の倍数を書き出すことになります。
p × 1, p × 2, … , p × pk-1 となります。
p に掛ける整数は、pk-1 よりも大きくなると、p との積が pk よりも大きくなってしまうことから、p に掛ける整数は、1 以上 pk-1 以下の範囲に入っていなければなりません。
よって、1 以上 pk 以下の範囲内の自然数から、これら pk-1 個の p の倍数を除いた残りの自然数は p で割り切れません。
そのため、pk との公約数は 1 しかもちません。
※ 公約数が 1 しかないということは、最大公約数が 1 ということです。
ゆえに、1 以上 pk 以下の自然数で pk との最大公約数が 1 である自然数の個数 φ(pk) が求まりました。
φ(pk) = pk － pk-1 です。
全体の pk 個の自然数から pk-1 個の p の倍数を除いた残りの自然数の個数が φ(pk) ということになります。
この右辺を pk でくくり出して、
φ(pk) = pk(1 － 1/p)
k = 1 のときは、
φ(p) = p(1 － 1/p) = p － 1 となり、先ほど求めたときと同じ結果になっています。
ここから、ファイ関数の乗法性という内容を解説します。この乗法性から自然数 n について、φ(n) の値を求めることができます。
ファイ関数-φ :φ(n)の乗法性
最大公約数が 1 である 2 以上の自然数 a と b が与えられたとします。
このとき、ab 以下の自然数で ab との最大公約数が 1 となっているものの個数 φ (ab) について、次の内容が成立します。
乗法的であることについて
【ファイ関数の乗法性】
最大公約数が 1 である自然数 a と b について、φ(ab) = φ(a)φ(b) である。
例えば、a = 3 と b = 4 について、
ab = 12 です。
12 以下の自然数で、12 との最大公約数が 1 となっているものは、1, 5, 7, 11 ですから、
φ(12) = 4 です。
3 以下の自然数で、3 との最大公約数が 1 となっているものは、1 と 2 ですから、
φ(3) = 2 です。
そして、4 以下の自然数で、4 との最大公約数が 1 となっているものは、1 と 3 ですから、
φ(4) = 2 です。
よって、
φ(12) = 4 = φ(3)φ(4)
このように、確かに成立しています。
ファイ関数の乗法性の証明は、後で群論の入門的な内容を使って証明をします。いったんは認めて議論を進めます。
このファイ関数の乗法性と、自然数 n の素因数分解から、φ(n) の値を求める式を導くことができます。
φ(n)の値を求める式
2 以上の自然数 n と、その素因数分解を
n = p1e1p2e2 … pkek とします。
p1e1, p2e2 , … , pkek たちは、どの二つについても最大公約数が 1 なので、
p1e1 と (p2e2 … pkek) に対してファイ関数の乗法性を用いると、
φ(n) = φ(p1e1(p2e2 … pkek))
= φ(p1e1)φ(p2e2 … pkek)
φ(p2e2 … pkek) についても、
同じ議論を繰り返すと、
φ(p1e1)φ(p2e2 … pkek)
= φ(p1e1)φ(p2e2) … φ(pkek) となります。
まとめると、
φ(n) = φ(p1e1)φ(p2e2) … φ(pkek)
素数ベキについては、既に値を求めているので、次のように計算ができます。
n の素因数分解で、それぞれの素因子となっている素数たちと、n の値だけとなっています。それぞれの指数の値たちが表に現れていない形の式で、φ(n) を表せています。
n が 2 以上のときに φ(n) の値を求める式です。
n = 1 のときには、φ(1) = 1 でしたので、理論上は、どんな自然数に対しても、φ(n) を表せるということになります。
ファイ関数-φ 剰余環とつなげて
2 以上の自然数 n に対して、剰余環 Z/nZ の乗法逆元とファイ関数は関連します。
剰余環についての基礎となる部品たちを説明します。
この記事では、整数環を Z と表しています。
Z/nZ が、これら二つの写像を加法と乗法とする可換環となっていることの確認は省略して、以下では、乗法についての乗法逆元をもつかどうかの確認方法を解説します。
以下、n を 2 以上として、Z/nZ の各元について乗法逆元をもつのかどうかを確認する方法を解説します。
そして、{0, 1, … , n － 1} を完全代表系として議論を進めていきます。
乗法逆元をもつかの確認
【定理】
余り-整数問題より
a と n を最大公約数が 1 である自然数とする。
このとき、x ÷ n と y ÷ n の余りが等しくないならば、ax ÷ n と ay ÷ n の余りが等しくない。
この【定理】の証明は、リンク先の以前に書いたブログ記事で解説をしています。
ax + nZ と ay + nZ について、
【定理】より、ax と ay を n で割ったときの余りが異なるので、Z における同値類として異なることが分かります。
そのため、ax + nZ ≠ ay + nZ です。
この考察から、a + Z/nZ の代表元 a と n の最大公約数が 1 であるならば、
(a0)+nZ, (a1)+nZ, … , a(n － 1)+nZ たちは、どの二つも異なる Z/nZ の元です。
これらは、異なる n 個の Z/nZ の元ですから、どれか 1 つのみが、1 + nZ と等しくなっています。
よって、
0 以上 n － 1 以下の自然数 k がただ 1 つのみ存在して、(ak) + nZ = 1 + nZ
左辺は a + nZ と k + nZ の積なので、
(a + nZ)(k + nZ) = 1 + nZ
これは、k + nZ ∈ Z/nZ が a + nZ の乗法逆元ということを示しています。
a と n の最大公約数が 1 であるとき、a + nZ は乗法逆元をもつということになります。
ファイ関数 φ(n) の定義は、n 以下の自然数で n との最大公約数が 1 となっている自然数の個数ということでした。
n ≧ 2 のときは、
n と n の最大公約数 n ≧ 2 なので、
(n － 1) 以下の自然数で n との最大公約数が 1 となっている自然数の個数が φ(n) となっています。
(n － 1) 以下の自然数で n との最大公約数が 1 となっている自然数を代表元にする Z/nZ の元は、乗法逆元をもちます。
そのため、φ(n) は Z/nZ の乗法逆元の個数を意味しています。
※ ただし、{0, 1, … , n － 1} に完全代表系を固定しているときです。
よって、n = p が素数であるとき、
Z/pZ は 1 + pZ, … , (p － 1) + pZ の代表元はすべて p との最大公約数が 1 となっています。
したがって、これら (p － 1) 個の元は乗法逆元をもちます。
記号ですが、(Z/nZ) の乗法逆元をもつ元全体を (Z/nZ)× と表すことにします。
n = p が素数のときには、
φ(p) = p － 1 が (Z/pZ)× に含まれている元の個数です。
零因子と合成数
自然数 n が 1 でも n でもない正の約数をもつとき、n を合成数といいます。
n が合成数だとすると、2 以上 n － 1 以下の範囲の自然数で、n の約数となるものが存在するということです。
※ n が合成数だとすると、必ず n は 4 以上ということになります。
合成数 n について、2 以上 n － 1 以下の約数を a とします。
約数の定義から、
n は、n = ab (b は整数) と表すことができます。
このとき、
n > 0 でなので、ab = n > 0 です。
a > 0 だから、b > 0 となります。
さらに、b = 1 とすると、
ab = a < n なので、ab = n に矛盾。
b = n とすると、n = an となり、a が 2 以上なので、矛盾です。
よって、b は 2 以上 n － 1 以下の自然数ということになります。この合成数 n について、Z/nZ の観点で考えてみます。
a + nZ, b + nZ ∈ Z/nZ です。
a も b も 2 以上 n － 1 以下の自然数なので、n で割り切れません。
同値類が等しいことの定義から、
a － 0 を n で割った余りが 0 でないため、
a + nZ ≠ 0 + nZ です。
同様にして、b + nZ です。
そして、
(a + nZ)(b + nZ) =
(ab) + nZ = n + nZ = 0 + nZ です。
環 Z/nZ の零元ではない a + nZ は、零元ではない b + nZ との積とると零元になりました。
一般に可換環の零元でない元について、その元との積が零となる零ではない元を零因子といいます。
可換環 Z/nZ において、
a + nZ の零因子が b + nZ ということになります。
可換環において、零因子が 1 つも存在しないとき、その可換環は整域といいます。
今の考察から、n が合成数のときには、Z/nZ は整域ではないということが分かりました。
ファイ関数-φ(n) 入門的な群論を用いて
以上の考察から、n が 2 以上のとき、
Z/nZ の元 x + nZ の代表元 x と n との最大公約数が 1 だと乗法逆元をもち、最大公約数が 2 以上だと乗法逆元をもたないということが分かりました。
0 以上 n － 1 以下の非負整数について、n との最大公約数が 1 となる数は、φ (n) となります。
n が 2 以上なので、n と 0、n と n の最大公約数が 2 以上なので、n との最大公約数が 1 となる自然数が 1 以上 n － 1 以下 の中にしか現れないからです。
有限個の元から成る集合もしくは集合の集まり S について、そこに含まれている元の個数を |S| と表すことにすると、
|(Z/nZ)×| = φ(n) となります。
この内容と中国剰余定理を用いて、ファイ関数が乗法的であることを証明します。
※ この定理の証明を、高校数学的な内容から始めて、リンク先で解説しています。
剰余環についての内容を押さえつつ、ファイ関数の内容の理解へとつなげにいきます。
乗法性の証明
【ファイ関数の乗法性】
自然数 a と b の最大公約数が 1 であるとき、
φ(ab) = φ(a)φ(b)
＜証明＞
a = 1 のとき、
φ(ab) = φ(b) = 1 × φ(b)
= φ(1)φ(b) = φ(a)φ(b) となり成立します。
b = 1 のときにも、同様にして成立します。よって、以下で、a ≧ 2 かつ b ≧ 2 のときを議論します。
a と b の最大公約数が 1 なので、
中国剰余定理から、
Z/(ab)Z と Z/aZ × Z/bZ が環として同型となります。
この同型についての環同型写像を f は、
f(x + (ab)Z)
= (x + aZ, x + bZ) となっています。
環の直積 Z/aZ × Z/bZ の元が乗法逆元をもつのは、第 1 成分と第 2 成分が両方とも逆元をもつときです。
(Z/aZ × Z/bZ)×
= (Z/aZ)× × (Z/bZ)× より、含まれている元の個数について、
|(Z/aZ × Z/bZ)×|
= |(Z/aZ)×| |(Z/bZ)×|
= φ(a)φ(b)
一方、f が環同型写像ですから、
Z/aZ × Z/bZ の乗法逆元全体である
(Z/aZ × Z/bZ)× に対応するものが、
f-1((Z/aZ × Z/bZ)×) = (Z/(ab)Z)× となります。
逆写像も全単射ですから、含まれている元の個数が等しくなり、
φ(ab) = |(Z/(ab)Z)×|
= |(Z/aZ × Z/bZ)×|
= φ(a)φ(b)【証明完了】
(Z/(ab)Z)× に含まれている元の個数は、ファイ関数を使って φ(ab) と表せることで、証明がスムーズに進みました。
さらに、ファイ関数についての基本的な性質を示します。
ファイ関数-φ 自然数nをファイ関数で分解
【よく使う内容】
自然数 x と y について、x と y の最大公約数を d としたとき、x/ d と y/d も自然数で、x/d と y/d の最大公約数が 1 となっている。
n = 10 を 2 以上の自然数とし、Z/10Z の完全代表系を {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} で固定します。
以下において、代表元は (10 － 1) 以下の非負整数だけを考えることにします。
そして、n = 10 の 2 以上の約数をすべて広い出します。
10 の 2 以上の約数は、2, 5, 10 です。これらを法とする Z/2Z, Z/5Z, Z/10Z という剰余環を用意します。
これらの剰余環において、乗法逆元たちをすべて集めた (Z/2Z)×, (Z/5Z)×, (Z/10Z)× たちに含まれている元の個数は、φ(2), φ(5), φ(10) でした。
実際に、乗法逆元をもつ元たちを書き出して確かめてみます。
【(Z/2Z)× の元たち】
2 以下の自然数で 2 との最大公約数が 1 となる数を代表元としますから、1 + 2Z の 1 個のみです。
→ φ(2) = 1
【(Z/5Z)× の元たち】
5 以下の自然数で 5 との最大公約数が 1 となる数が代表元です。
1 + 5Z, 2 + 5Z, 3 + 5Z, 4 + 5Z の 4 個
→ φ(5) = 4
【(Z/10Z)× の元たち】
10 以下の自然数で 10 との最大公約数が 1 となる数が代表元です。
1 + 10Z, 3 + 10Z, 7 + 10Z, 9 + 10Z の 4 個
→ φ(10) = 4
1 + 4 + 4 = 10 － 1
φ(2) + φ(5) + φ(10)
= 10 － 1
φ(1) = 1 を辺々足すと、
φ(1) + φ(2) + φ(5) + φ(10)
= 10
はじめに与えられた n = 10 について、2 以上の n の正の約数たちについてのファイ関数の値たちのすべての和を計算すると n － 1 となるということです。
φ(1) = 1 を辺々足すと、n の正の約数をすべて足し合わせると n になります。
(Z/2Z)×, (Z/5Z)×, (Z/10Z)× のそれぞれの 1 つの元と 1 以上 10 － 1 以下の自然数を対応させる全単射で、うまく分類することが決め手になっています。
例えば、(Z/5Z)× の元 3 + 5Z については、はじめに与えられた 10 を法としている 5 で割った商 10/5 を 3 に掛けることで、
(10/5) × 3 = 2 × 3 = 6 を対応させます。
この対応は実は全単射で、逆対応は、まず 6 と 10 の最大公約数を求めます。2 が最大公約数です。
そして、10/2 = 5 を法とする (Z/5Z)× の元 である(6/2) + (10/5)Z = 3 + 5Z を対応させます。
この仕組みを使って、以下の証明をします。
正確な証明
n = 1 のときは、φ(1) = 1 で成立するので、以下、n が 2 以上の自然数のときの証明です。
＜証明＞
n を 2 以上の自然数とし、n の 2 以上のすべての正の約数を k1, … , kt とします。
A = (Z/k1Z)×∪…∪(Z/ktZ)×,
B = {1, 2, … , n － 1}
A は各剰余環の元である集合たちをすべて集めた集まりです。
【f : A → B の定義】
x + kiZ ∈ (Z/kiZ)× (ただし自然数 i は 1 以上 t 以下で、1 ≦ x ≦ ki － 1) に対して、n/ki = n ÷ ki は n の正の約数です。
f(x + kiZ) = (n/ki)x と定義します。
※ (Z/kiZ)× の代表元を 1 以上 ki － 1 以下の整数に固定した、代表元の取り方に依存する写像です。
n/ki と x は n の正の約数なので、
(n/ki)x は正の整数となります。
1 ≦ x ≦ ki － 1 より、
(n/ki)x ≦ (n/ki)(ki － 1)
< (n/ki)ki = n
1 ≦ (n/ki)x ≦ n － 1 より、
f(x + kiZ) = (n/ki)x ∈ B です。
【g : B → A の定義】
y ∈ B に対して、n と y の最大公約数を y’ とします。
n/y’ を法として、
g(y) = (y/y’) + (n/y’)Z ∈ Z/(n/y’)Z と定義します。
1 ≦ y ≦ n － 1 なので、n ÷ (n/y’) = y’ となり、y’ は正の整数なので、n/y’ は n の正の約数です。
※ 1 = n/n < n/(n － 1) ≦ n/y’ なので、n/y’ は 2 以上の n の正の約数。そのため、k1 から kt のどれかとなっています。
y/y’ と n/y’ は正の整数であり、最大公約数が 1 です。
そのため、(y/y’) + (n/y’)Z は乗法逆元をもつので、(Z/(n/y’)Z)× の元です。
そして、1 ≦ y < n より、1 ≦ y/y’ < n/y’
つまり、1 ≦ y/y’ ≦ n/y’ － 1 なので、固定している代表元の値となっています。
したがって、
g(y) = (y/y’) + (n/y’)Z ∈ Z/(n/y’)Z ⊂ A となっています。
【 f が全単射である理由】
まず、gf が恒等写像であることを示します。
x + kiZ ∈ (Z/kiZ)× (ただし自然数 i は 1 以上 m 以下で、1 ≦ x ≦ ki － 1) に対して、
(gf)(x + kiZ)
= g(f(x + kiZ)) = g((n/ki)x)
(n/ki)x と n の最大公約数は n/ki となります。最大公約数となっていることは後で示します。
g の定義から n/(n/ki) = ki を法として、(n/ki)x/(n/ki) = x を代表元とする値を対応させます。
そのため、g((n/ki)x) = x + kiZ です。
よって、(gf)(x + kiZ) = x + kiZ となります。したがって、gf は恒等写像となります。
飛ばしていた、「(n/ki)x と n の最大公約数 d は n/ki となる」ことを示します。
(n/ki) | (n/ki)x, (n/ki) | n なので、n/ki は (n/ki)x と n の公約数なので n/ki ≦ d です。
また、公約数は最大公約数の約数となるので、ある正の整数 p が存在して、d = (n/ki)p と表せます。
d | n より (n/ki)p | n なので、次の割り算は割り切れます。
n ÷ (n/ki)p
= n ÷ (np/ki)
= n × (ki/np) = ki/p
よって、p は ki の正の約数です。
また、d | (n/ki)x なので、次の割り算は割り切れます。
(n/ki)x ÷ (n/ki)p = x ÷ p
よって、p は x の正の約数です。
これらのことから、p は x と ki の公約数ということになります。
一方、x + kiZ ∈ (Z/kiZ)× だから x と ki の最大公約数は 1 です。
これより、p = 1 で、
d = (n/ki)p = (n/ki) となります。
次に、fg が恒等写像となることを示します。
y ∈ B とし、y と n の最大公約数を y’ とします。
(fg)(y) = f((y/y’) + (n/y’)Z) です。
n/(n/y’) = y’ より、f の定義から、
f((y/y’) + (n/y’)Z)
= y'(y/y’) = y
よって、(fg)(y) = y となり、fg は恒等写像です。
以上から gf と fg がともに恒等写像ということが示せたので、f は全単射です。
したがって、A に含まれる元の個数が B に含まれる元の個数 (n － 1) に一致します。
A に含まれる元の個数は、
φ(k1) + … + φ(kt) なので、
φ(k1) + … + φ(kt) = n － 1
φ(1) = 1 を辺々足すと、
φ(1) + φ(k1) + … + φ(kt) = n
左辺は n の正の約数すべての和なので、結論が導けました。【証明完了】
関連する整数の記事として、
合同方程式の解き方という記事を投稿しています。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。