\phi(n)n보다 작은 자연수 중 n과 서로소인 개수를 세는 수론적 함수이다.n 이하의 자연수 중에서 n과 서로소인 것의 갯수로 정의된다.\phi(n)=\# \{k\le n : (n,k)=1\}\phi(n)=\sum_{a \leq n, (a,n)=1}1\phi(n) = \sum_{k=1}^n 1\begin{aligned} \phi(x)&=\sum_{k=1}^{n} \left[ \frac{1}{(n,k)} \right]=\sum_{k=1}^{n} \sum_{d \mid (n,k)} \mu(d)\\&=\sum_{k=1}^{n} \sum_{d \mid n,\ d \mid k} \mu(d) \sum_{d \mid q} \sum_{q=1}^{n/d} \mu(d)\ (\text{let.}\ k=qd)\\&=\sum_{d \mid n} \mu(d) \frac{n}{d} \end{aligned}
\sum_{d \mid n} \mu(d) = \left[ \frac{1}{n} \right]임은 뫼비우스 함수를 참고하라.\begin{aligned} n \prod_{p \mid n}\left(1-\frac{1}{p}\right)&=n(1+\sum_{p_1 \mid n} \frac{-1}{p_1}+\sum_{p_1 \mid n,\ p_2 \mid n,\ p_1 \neq p_2} \frac{1}{p_1p_2}+ \cdots)\\&=\sum_{d \mid n} \mu(d) \frac{n}{d}\\&=\phi(n) \end{aligned}
\phi가 곱셈적이라는 것을 알 수 있다. 사실, m,n \in \Bbb N에 대해 다음이 성립한다.\phi(mn)=\phi(m)\phi(n)\frac{(m,n)}{\phi((m,n))}
(m,n)은 m,n의 최대공약수이다.\phi(n)=\sum_{d \mid n}\mu(d)\frac{n}{d}에서 뫼비우스 반전을 이용하면 간단하게 증명되지만, 이렇게 증명할 수도 있다.n의 약수 d에 대하여 집합 A_d을 n과의 최대공약수가 d인 자연수들의 집합으로 정의하면, 임의의 A_{d_i}, A_{d_j}은 서로소이며 \bigcup_{d|n} A_d=\{1,2, \cdots, n\}이다. 그런데 |A_d|=\phi(\frac{n}{d})이므로\sum_{d|n} \phi(\frac{n}{d})=n
n\geq3에 대해 다음이 성립한다.\phi(n)\ge{n\over\log\log n}(e^{-\gamma}+O(1/\log\log n))n이 무한히 많이 존재한다.\gamma는 오일러 상수이다.\phi(n)\gg n/\log\log n
\mathcal R을 모든 m<n에 대해 \phi(m)/m<\phi(n)/n인 자연수 n의 집합으로 정의하자.\omega(n)=k (n의 서로 다른 소인수의 개수)에 대해 n^*를 첫 k개 소수의 곱으로 두면, n\neq n^*일 경우 n^*<n, \phi(n^*)/n^*<\phi(n)/n이 성립한다.n\not\in\mathcal R이 되므로 \mathcal R의 원소는 모두 다음의 형태를 띤다.n=\prod_{p\leq y}p\log를 취하면 \log n=\vartheta(y)\asymp y이고, 다시 \log를 취하면 \log\log n=\log y+O(1)을 얻는다.\prod_{p\leq x}\left(1-\frac1p\right)^{-1}=e^\gamma\log x+O(1)에 의해{\phi(n)\over n}=\prod_{p\leq y}\left(1-\frac1p\right)={e^{-\gamma}\over\log y}(1+O(1/\log y))n\not\in\mathcal R일 경우, m<n이고 \phi(m)/m<\phi(n)/n인 m\in\mathcal R이 존재한다. 그러면\displaystyle {\phi(n)\over n}>{\phi(m)\over m}={1\over\log\log m}(e^{-\gamma}+O(1/\log\log m))\ge{1\over\log\log n}(e^{-\gamma}+O(1/\log\log n))\phi(p^a)=p^a-p^{a-1}\phi(mn)=\phi(m)\phi(n)((m,n)/\phi((m,n)))a \mid b \Rightarrow \phi(a) \mid \phi(b)n이 r개의 서로 다른 홀소수를 가지면 2^r \mid \phi(n)