オイラーのφ関数の性質

代数の勉強中なのですが、DataFramesを使って、[オイラーのφ関数(totient関数)](https://ja.wikipedia.org/wiki/オイラーのφ関数)の性質：
$$
\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に格納します。
そして、カラムの名前を適切な名前に変えて出力しました。

```julia
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入門のための参考資料まとめ](https://qiita.com/yamasushi/items/e3eded4bfa42dcc4ec42)