オイラーの φ 関数Ⅱ - NMP WS math index / 永田学習塾

オイラーの φ 関数Ⅱ
前回オイラーの φ 関数Ⅰで乗法性 φ(ab) = φ(a)･ φ(b) を示しましたが, この式と以下に述べる
(
1
φ( p e) = p e 1 −
p
)
(
を用いると φ(n) = n 1 −
1
p1
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
という
関係式が導かれます.　実際の計算ではこの式を使うと楽になります.
そしてこの式を眺めていると何となく余事象の確率っぽく見えてしまうのですが・・・
注*上の各式において
・ a , b は互いに素
・ n は自然数(正の整数)
・ p1, p2, ⋯ , pi は n の素因数（素数の累乗で表したときの底(基数)のこと)
*
例えば n = 2000 ならば 2000 = 24 × 53 なので p1 = 2, p2 = 5 .
■証明
証明することは------------------------------------------------------------------自然数 n の素因数を p1, p2, ⋯ , pi 素因数とするとき,
(
φ(n) = n 1 −
1
p1
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
が成立する｡
---------------------------------------------------------------------------------------[証明]
まず n = p
e
となる場合（ p は素数）
p は素数だから pe と互いに素でない数は
( e−1)
p×1, p×2, p×3,･････ , p× p e−1 の p
よって
個
e
e
p と互いに素なものの個数 φ( p ) は
e
e
φ( p ) = p − p
e−1
=p
e
(
1−
p
e−1
pe
)
=p
e
(
1−
1
p
)
となります.
これと前回の「オイラーの φ 関数Ⅰ」で示した乗法性 φ(ab) = φ(a)･ φ(b)
a , b は互いに素) を使うと以下のようになります.
(ただし
e
e
1
2
n を素因数分解して n = p 1 ⋅ p
2
⋯ p
e
i
i
となったとします.
このとき
( )( ) ( )
φ(n) = φ p
=p
(
e
1
1
e1
1
(
⋅φ p
e2
2
e
e2
1
2
(
i
) (
⋯ p
ei
i
2
⋅ 1−
⋯ p
i
i
1−
1
1
⋅ 1−
p
p
⋯
1
p
i
1
1
1
⋅ 1−
p
p
1
)
e
( )
)( )( ) ( )
)( ) ( )
1
= n⋅ 1 −
ei
e
1
1
⋅p 2 1 −
2
p
p
1−
= p 1⋅ p
⋯ φ p
1−
⋯
2
1−
2
1
p
i
1
p
i
ということで証明できました.
■計算例
0 から n までの, n と互いに素な数の個数の例
30 と互いに素な数は 30 = 2 × 3 × 5 なので
(
φ(30) = φ(2×3×5) = 30 1 −
)(
)(
)
1
1
1
⋅ 1− ⋅ 1−
=8
2
3
5
8 個.
600 と互いに素な数は 600 = 23 × 3 × 52 なので
(
φ(600) = φ(23 ×3×52 ) = 600 1 −
)(
)(
)
1
1
1
⋅ 1− ⋅ 1−
= 160
2
3
5
160 個.
■眺めてみると
(
φ(n) = n 1 −
1
p1
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
この式を眺めてると, 余事象の確率に見えてきました. さらに n を掛けてるところから期待
値？っぽくも見えてきます. 1 から n までの数が書いてあるサイコロを振ったとき出る目が
n と互いに素である数の期待値は？という感じでしょうか.
■考えてみる
(
φ(n) = n 1 −
φ(n) = p
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
の一歩手前(もしくは２歩手前)は
( ) ( ) ( )
e1
1
1
p1
1−
p
e 1−1
1
p
⋅p
e2
2
e1
1−
p
e2 −1
2
p
1
e2
⋯ p
ei
i
1−
p
e i−1
i
p
2
ei
でした.
i
e
e
e
とりあえず i = 3 としてみると, n = p 1⋅p 2⋅p 3 ,
1
2
3
( ) ( ) ( )
( )
φ(n) = p
上の式の
e1
1
1−
1−
e1
1
e 1−1
1
p
p
⋅p
e1
2
1−
p
e2 −1
2
p
1
1
e1
e2
⋅p
e3
3
1−
p
e 3 −1
3
p
2
e3
です.
3
だけを取り出して余事象の確率を頭に浮かべながら見てみると, この
1
の中から p
そしてそれらの積
e2
e1 −1
p
式が 1 ~ p
p
e1
1
と互いに素な数を引き当てる確率になっているように見えます.
( )( )( )
1−
p
e1 −1
1
p
e1
1
⋅ 1−
p
e 2 −1
2
p
e2
2
⋅ 1−
p
e3 −1
3
p
e3
e
e
e
は n = p 1⋅p 2⋅p 3 で
1
2
3
3
あることを思い出すと, n と互いの素な数を引き当てる確率と解釈できます.(補足参照)
そしてこれにさらに n を掛けたものが φ(n) となるわけですが・・・
■どう解釈するのか？
1 ~ n までの数から n と互いの素な数を引き当てる確率に n を掛けると何が出るのか？
単純に期待値でいいのか？ φ(n) が期待値？いまいちイメージが頭に浮かばないですが･･･
何が問題かというと, 個数のイメージと期待値のイメージがつながらないのです.
なのでこう考えることにします.
確率＝比率(割合)
つまり 1 から n までの n 個の数の中に
(
1−
1
p1
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
の比率で
n と互いに素な数が存在するとするわけです(式はもとの i の式に戻ってます).
(
そうすると φ(n) = n 1 −
1
p1
)(
1−
) (
1
1
･･･ 1 −
p2
pi
)
の式がなんとなく身近に見えて
きます.
ただし, 今言ってきたことはあくまでイメージで, 個人的にそう見えるというだけで, 証明した
わけではありません. ただこの式を覚えるときのイメージとしてはいいのではないかと思いま
す.
■補足
互いに素な数 a , b , c があり, それらと互いに素でない数の集合をそれぞれ A , B , C とす
ると A ∪ B ∪ C = A ∩ B ∩ C なのでそれらの個数についても同様な式が成り立ち, そのこ
とからそれらの確率についても同様とし, 積 abc と互いに素な数を引き当てる確率 P は
P ( A ∩ B ∩ C ) = P ( A ∪ B ∪ C ) = P ( 1 − A ∪ B ∪ C ) であると考えました.
■終わりに
オイラーの φ 関数そのものというよりも, 式の形が確率っぽいのが気になって文章にしてみま
したが確率というよりは比率と考えた方がわかりやすいようです. 厳密さよりイメージ優先と
いう観点からはいいのではないでしょうか.
©長崎県大村市永田学習塾

Download Report