オイラーのトーシェント関数の定義
オイラーのトーシェント関数
自然数\(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*}
自然数\(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*}
\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*}
ページ情報
| タイトル | オイラーのトーシェント関数の定義 |
| URL | https://www.nomuramath.com/ns6xjj09/ |
| SNSボタン |
ユークリッドの互除法
\[
\gcd(a,b)=\gcd(b,r)
\]
(*)原始根定理
\[
\varphi(p-1)
\]
n番目の素数の式
\[
P\left(n\right)=1+\sum_{k=1}^{2^{n}}\left\lfloor \sqrt[n]{\frac{n}{\sum_{j=1}^{k}\left\lfloor \cos^{2}\left(\frac{\left(j-1\right)!+1}{j}\pi\right)\right\rfloor }}\right\rfloor
\]
オイラーの規準
\[
QR(a,p)\overset{p}{\equiv}a^{\frac{p-1}{2}}
\]