LoginSignup
3
4

More than 5 years have passed since last update.

オイラーのφ関数の性質

Last updated at Posted at 2019-05-09

代数の勉強中なのですが、DataFramesを使って、オイラーのφ関数(totient関数)の性質:
$$
\sum_{m \mid n} \varphi(m) = n
$$
を確認してみました。

nの任意の約数をdとするとき,n個の数1,2,……,nの中に(x,n)=dであるxはいくつあるか.
「初等整数論講義 第二版」(高木貞治)P.46

nを決めて、1からnまでの数iについて、nとの最大公約数(n,i)を求めます。それをDataFrameのgcd_n_iに保存します。そして、n/(n,i)の値でソートします。

gcd_n_iとdiv_n_gcdはnの約数全体を表しています。そして、totient関数の総和はnになっています。

このとき、nの約数m(コードではdiv_n_gcd)に対応する単数群$ (\mathbb{Z}/m\mathbb{Z})^\times $がdiv_i_gcdのカラムに現れます。それを抽出しz_zmsに格納します。
そして、カラムの名前を適切な名前に変えて出力しました。

using DataFrames
using Primes

n=30
@show(n)
gcds = gcd.(n,1:n)
df=DataFrame(
    i          = 1:n
    , gcd_n_i  = gcds
    , div_n_gcd= div.(n  ,gcds)
    , div_i_gcd= div.(1:n,gcds)
    )
sort!(df,:div_n_gcd)

gcd_n_i   =unique(df.gcd_n_i)
div_n_gcd =unique(df.div_n_gcd)

z_zms =
    map(div_n_gcd) do m
        m , 
        rename(df[ df.div_n_gcd .== m , [:i,:div_i_gcd]] , 
            :div_i_gcd=>Symbol("(Z/Z$m)×"))
    end

totient_gcd_n_i  =totient.(gcd_n_i)
totient_div_n_gcd=totient.(div_n_gcd)
println("(n,i)=$gcd_n_i , totients=$totient_gcd_n_i , sum=$(sum(totient_gcd_n_i))")
println("n/(n,i)=$div_n_gcd , totients=$totient_div_n_gcd , sum=$(sum(totient_div_n_gcd))")

rename!(df,
    :gcd_n_i  =>Symbol("(n,i)")   ,
    :div_n_gcd=>Symbol("n/(n,i)") ,
    :div_i_gcd=>Symbol("i/(n,i)"))

println("")
show(df)
println("\n")

for (m,z_zm) in z_zms
    #@show(z_zm)
    println("m=$m , totient=$(totient(m))")
    show(z_zm)
    println("\n")
end
n = 30
(n,i)=[30, 15, 10, 6, 5, 3, 2, 1] , totients=[8, 8, 4, 2, 4, 2, 1, 1] , sum=30
n/(n,i)=[1, 2, 3, 5, 6, 10, 15, 30] , totients=[1, 1, 2, 4, 2, 4, 8, 8] , sum=30

30×4 DataFrame
│ Row │ i     │ (n,i) │ n/(n,i) │ i/(n,i) │
│     │ Int64 │ Int64 │ Int64   │ Int64   │
├─────┼───────┼───────┼─────────┼─────────┤
│ 1   │ 30    │ 30    │ 1       │ 1       │
│ 2   │ 15    │ 15    │ 2       │ 1       │
│ 3   │ 10    │ 10    │ 3       │ 1       │
│ 4   │ 20    │ 10    │ 3       │ 2       │
│ 5   │ 6     │ 6     │ 5       │ 1       │
│ 6   │ 12    │ 6     │ 5       │ 2       │
│ 7   │ 18    │ 6     │ 5       │ 3       │
│ 8   │ 24    │ 6     │ 5       │ 4       │
│ 9   │ 5     │ 5     │ 6       │ 1       │
│ 10  │ 25    │ 5     │ 6       │ 5       │
│ 11  │ 3     │ 3     │ 10      │ 1       │
│ 12  │ 9     │ 3     │ 10      │ 3       │
│ 13  │ 21    │ 3     │ 10      │ 7       │
│ 14  │ 27    │ 3     │ 10      │ 9       │
│ 15  │ 2     │ 2     │ 15      │ 1       │
│ 16  │ 4     │ 2     │ 15      │ 2       │
│ 17  │ 8     │ 2     │ 15      │ 4       │
│ 18  │ 14    │ 2     │ 15      │ 7       │
│ 19  │ 16    │ 2     │ 15      │ 8       │
│ 20  │ 22    │ 2     │ 15      │ 11      │
│ 21  │ 26    │ 2     │ 15      │ 13      │
│ 22  │ 28    │ 2     │ 15      │ 14      │
│ 23  │ 1     │ 1     │ 30      │ 1       │
│ 24  │ 7     │ 1     │ 30      │ 7       │
│ 25  │ 11    │ 1     │ 30      │ 11      │
│ 26  │ 13    │ 1     │ 30      │ 13      │
│ 27  │ 17    │ 1     │ 30      │ 17      │
│ 28  │ 19    │ 1     │ 30      │ 19      │
│ 29  │ 23    │ 1     │ 30      │ 23      │
│ 30  │ 29    │ 1     │ 30      │ 29      │

m=1 , totient=1
1×2 DataFrame
│ Row │ i     │ (Z/Z1)× │
│     │ Int64 │ Int64   │
├─────┼───────┼─────────┤
│ 1   │ 30    │ 1       │

m=2 , totient=1
1×2 DataFrame
│ Row │ i     │ (Z/Z2)× │
│     │ Int64 │ Int64   │
├─────┼───────┼─────────┤
│ 1   │ 15    │ 1       │

m=3 , totient=2
2×2 DataFrame
│ Row │ i     │ (Z/Z3)× │
│     │ Int64 │ Int64   │
├─────┼───────┼─────────┤
│ 1   │ 10    │ 1       │
│ 2   │ 20    │ 2       │

m=5 , totient=4
4×2 DataFrame
│ Row │ i     │ (Z/Z5)× │
│     │ Int64 │ Int64   │
├─────┼───────┼─────────┤
│ 1   │ 6     │ 1       │
│ 2   │ 12    │ 2       │
│ 3   │ 18    │ 3       │
│ 4   │ 24    │ 4       │

m=6 , totient=2
2×2 DataFrame
│ Row │ i     │ (Z/Z6)× │
│     │ Int64 │ Int64   │
├─────┼───────┼─────────┤
│ 1   │ 5     │ 1       │
│ 2   │ 25    │ 5       │

m=10 , totient=4
4×2 DataFrame
│ Row │ i     │ (Z/Z10)× │
│     │ Int64 │ Int64    │
├─────┼───────┼──────────┤
│ 1   │ 3     │ 1        │
│ 2   │ 9     │ 3        │
│ 3   │ 21    │ 7        │
│ 4   │ 27    │ 9        │

m=15 , totient=8
8×2 DataFrame
│ Row │ i     │ (Z/Z15)× │
│     │ Int64 │ Int64    │
├─────┼───────┼──────────┤
│ 1   │ 2     │ 1        │
│ 2   │ 4     │ 2        │
│ 3   │ 8     │ 4        │
│ 4   │ 14    │ 7        │
│ 5   │ 16    │ 8        │
│ 6   │ 22    │ 11       │
│ 7   │ 26    │ 13       │
│ 8   │ 28    │ 14       │

m=30 , totient=8
8×2 DataFrame
│ Row │ i     │ (Z/Z30)× │
│     │ Int64 │ Int64    │
├─────┼───────┼──────────┤
│ 1   │ 1     │ 1        │
│ 2   │ 7     │ 7        │
│ 3   │ 11    │ 11       │
│ 4   │ 13    │ 13       │
│ 5   │ 17    │ 17       │
│ 6   │ 19    │ 19       │
│ 7   │ 23    │ 23       │
│ 8   │ 29    │ 29       │

1...nの整数が単数群の要素に対応していることが確認できました。

参考

3
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
4