ファイ関数-φ(n) | n以下の自然数でnと互いに素なものの個数
ファイ関数 φ(n) （トーシェント関数）は、1 以上 n 以下の自然数の中で、n との最大公約数が 1 である自然数の個数を表しています。
まず高校の範囲でファイ関数の基本的な性質を解説します。
自然数 a と b の最大公約数が 1 のとき、
φ(ab) = φ(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 と表します。
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)の乗法性
最大公約数が 1 である 2 以上の自然数 a と b が与えられたとします。
このとき、ab 以下の自然数で ab との最大公約数が 1 となっているものの個数 φ (ab) について、次が成立します。
【ファイ関数の乗法性】
最大公約数が 1 である自然数 a と b について、
φ(ab) = φ(a)φ(b) である。
ファイ関数の乗法性の証明は、後で証明します。いったんは認めて議論を進めます。
このファイ関数の乗法性と、自然数 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)× に含まれている元の個数です。
※ 可換環において、零因子が 1 つも存在しないとき、その可換環を整域といいます。
※ n が合成数のときには、Z/nZ は整域ではありません。
入門的な群論を用いて
以上より、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 以下 の中にしか現れないからです。
|(Z/nZ)×| = φ(n) となります。
※ |S| は S の位数を表す記号です。
この内容と中国剰余定理を用いて、ファイ関数の乗法性を示します。
乗法性の証明
【ファイ関数の乗法性】
自然数 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)【証明完了】
さらに、ファイ関数についての基本的な性質で、
自然数nの分割という内容があります。
【関連する整数の記事】
これで、今回の記事を終了します。
読んで頂き、ありがとうございました。