代数の勉強中なのですが、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の整数が単数群の要素に対応していることが確認できました。
参考
- 「代数入門ー群と加群」(堀田良之)P.53
- 「初等整数論講義 第二版」(高木貞治)P.46
- Julia入門のための参考資料まとめ