DAY 6 オイラーのファイ関数 - 仮面浪人生の日記

今回は上記について学習した。

定義

1から自然数nまでの数の中でnと互いに素な自然数の数を $\phi(n)$ とする。

性質

1. $p$ が素数のとき $\phi(p)=p-1$

2. $p$ が素数、 $k$ が整数のとき $\phi(p^k)=p^k-p^{k-1}$

3. $p$ と $q$ が異なる素数のとき $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

4. $p$ と $q$ が互いに素のとき $\phi(pq)=\phi(p)\phi(q)$

証明

pが素数であるということはpと互いに素ではない自然数はpの倍数のみであるということである。

pより小さい自然数にpの倍数は存在しないので、 $\phi(p)=p-1$

$p^k$ までの自然数でpと互いに素ではない自然数の個数は $p^{k-1}$ である。

したがって $\phi(p^k)=p^k-p^{k-1}$

$pq$ までの自然数でpqと互いに素ではない自然数の個数は $p+q-1$ ( $q$ の倍数の個数 $p$ 、 $p$ の倍数の個数 $q$ 、 $pq$ はどちらにも含まれるから $-1$ )

したがって $\phi(pq)=pq-(p+q-1)=pq-p-q+1=p(q-1)-(q-1)=(p-1)(q-1)$

省略.軽く調べてみたが少し高等的すぎる。数学コース在学で理解できないというのも不甲斐ないものだが...いつかは。

以上である。

今日は昨日書いたとおり早起き(6時起き）したがあまりよく眠れず午前中はほとんど寝ていてしまった。

まともに活動を開始したのは午後５時ごろだったので、少し考えものである。

合計：1時間1分