オイラーのトーシェント関数の定義

by nomura · 2020年9月5日

オイラーのトーシェント関数
自然数\(n\in\mathbb{N}\)に対し、\(n\)と互いに素である1以上\(n\)以下の個数をオイラーのトーシェント関数といい、\(\phi\left(n\right)\)で表す。
\begin{align*} \phi\left(n\right) & =\left|\left\{ k\in\mathbb{N};k\in\left\{ 1,2,\cdots,n\right\} ,\gcd\left(k,n\right)=1\right\} \right|\\ & =\sum_{k\in\left\{ 1,2,\cdots,n\right\} ,\gcd(k,n)=1}1\\ & =\sum_{k\in\left\{ 0,1,2,\cdots,n-1\right\} ,\gcd\left(k,n\right)=1}1 \end{align*}

\[ \sum_{k\in\left\{ 1,2,\cdots,n\right\} ,\gcd(k,n)=1}1=\sum_{a\in\left\{ 0,1,2,\cdots,n-1\right\} ,\gcd\left(a,n\right)=1}1 \] となることを示す。
\begin{align*} \sum_{k\in\left\{ 0,1,2,\cdots,n-1\right\} ,\gcd\left(k,n\right)=1}1 & =\begin{cases} \sum_{k\in\left\{ 1,2,\cdots,n-1\right\} ,\gcd\left(k,n\right)=1}1 & n\in\left\{ 2,3,\cdots\right\} \\ 1+\sum_{k\in\left\{ 1,2,\cdots,n-1\right\} ,\gcd\left(k,n\right)=1}1 & n=1 \end{cases}\\ & =\begin{cases} \sum_{k\in\left\{ 1,2,\cdots,n\right\} ,\gcd\left(k,n\right)=1}1 & n\in\left\{ 2,3,\cdots\right\} \\ \sum_{k\in\left\{ 1,2,\cdots,n\right\} ,\gcd\left(k,n\right)=1}1 & n=1 \end{cases}\\ & =\sum_{k\in\left\{ 1,2,\cdots,n\right\} ,\gcd\left(k,n\right)=1}1 \end{align*}