오일러 피 함수 더 알아보기

오일러 피 함수는 $n$ 의 소인수에 대한 곱으로도 표현될 수 있는데, 그 식은 다음과 같습니다.

 

$n \geq 1$ 일 때 $$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

 

Proof

$n = 1$ 일 때, $p \mid 1$ 인 소수 $p$ 가 없으므로 아무것도 곱해지지 않은 결과인 $1$ 이 됩니다.

$n > 1$ 일 때, $p_1, \cdots, p_r$ 을 $n$ 의 서로 다른 소인수라고 하겠습니다 그러면 위 식의 곱은 $$\begin{align*}
\prod_{p\mid n}\left(1 - \frac{1}{p}\right) &= \prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right) \\
&= 1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_i p_j} - \sum \frac{1}{p_i p_j p_k} + \cdots + \frac{(-1)^r}{p_1 p_2 \cdots p_r}
\end{align*}$$ 여기서 $\sum \frac{1}{p_i p_j}$ 와 같은 것은, 가능한 $i, j$ 에 대해 모두 더하라는 뜻입니다. 그런데 우변에서 분모는 모두 $d \mid n$ 인 $d$ 중 제곱 인수가 없는 것, 즉 소수의 제곱이 곱해지지 않은 것이고 분자의 $\pm 1$ 은 $\mu (d)$ 와 같음을 알 수 있습니다. 따라서 위의 합을 다시 쓰면 $$\sum_{d\mid n}\frac{\mu(d)}{d}$$ 이고, 따라서 $$\phi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right) = \sum_{d\mid n}\mu(d)\frac{n}{d}$$ 가 되어 증명이 완성됩니다.

 

오일러 피 함수의 많은 성질은 위의 곱 표현으로부터 유도하는 것이 더 쉬운 경우가 많습니다. 예시로, 아래의 성질들을 보겠습니다.

 

오일러 피 함수는 아래의 성질을 만족한다. (a) $\phi(p^a) = p^a - p^{a-1}$ (단 $p$ 는 소수, $a \geq 1$) (b) $\phi(mn) = \phi(m)\phi(n)\frac{d}{\phi(d)}$ (단, $d = (m, n)$) (c) $a \mid b \Rightarrow \phi(a) \mid \phi(b)$ (d) 만약 $n \geq 3$ 이라면 $2\mid \phi(n)$ 이고, $n$ 이 $r$ 개의 서로 다른 홀수 소인수를 가지면 $2^r \mid \phi(n)$

 

Proof

(a) $$\phi(p^a) = p^a \prod_{q \mid p^a}\left(1 - \frac{1}{q}\right) = p^a \left(1 - \frac{1}{p}\right) = p^a - p^{a-1}$$

(b) $$\frac{\phi(n)}{n} = \prod_{p\mid n}\left(1 - \frac{1}{p}\right)$$ 로 적을 수 있습니다. $mn$ 의 소인수는 $m$ 의 소인수이거나 $n$ 의 소인수입니다. 만약 $p$ 가 $m, n$ 모두의 소인수라면 $p \mid (m, n)$ 도 성립합니다. 따라서 $$\frac{\phi(mn)}{mn} = \prod_{p \mid mn}\left( 1- \frac{1}{p}\right) = \dfrac{\displaystyle\prod_{p \mid m}\left( 1 - \frac{1}{p}\right)\prod_{p \mid n}\left( 1 - \frac{1}{p}\right)}{\displaystyle\prod_{p \mid (m, n)}\left( 1 - \frac{1}{p}\right)} = \dfrac{\dfrac{\phi(m)}{m}\dfrac{\phi(n)}{n}}{\dfrac{\phi(d)}{d}}$$ 이므로 양변에 $mn$ 을 곱해 증명을 완성합니다.

 

(c) $a \mid b$ 라면, 어떤 $1 \leq c \leq b$ 가 존재해 $b = ac$ 입니다. 만약 $b = c$ 이면 $a = 1$ 이고, 이 때 (c) 는 참이므로 $c < b$ 일 때를 보겠습니다. 이 때, (b) 로부터 $$\phi(b) = \phi(ac) = \phi(a)\phi(c) \frac{d}{\phi(d)} = d\phi(a) \frac{\phi(c)}{\phi(d)}$$ 입니다. 이 때 $d = (a, c)$ 로 두었습니다. 이제 $b$ 에 대한 귀납법으로 증명을 끝내겠습니다.

만약 $b= 1$ 이면 자명하게 참입니다.

$1, 2, \cdots b - 1$ 에 대해 (c) 가 항상 성립한다고 가정하면 $c < d$ 이고 $d\mid c$ 이므로 $\phi(d) \mid \phi(c)$ 가 성립합니다. 따라서 $$\phi(b)  = d \frac{\phi(c)}{\phi(d)}\phi(a)$$ 이므로 (c) 가 증명됩니다.

 

(d) 만약 $n = 2^a$ (단, $a \geq 2$) 이면 (a) 에 의해 $\phi(n)$ 은 짝수입니다. 이제 $n$ 이 적어도 하나의 홀수 소인수를 가질때를 보겠습니다. 그 때 $\phi(n)$ 은 $$\phi(n) = n \prod_{p\mid n} \frac{p-1}{p} = \frac{n}{\displaystyle\prod_{p\mid n}}\prod_{p\mid n}(p-1) = c(n) \prod_{p\mid n}(p-1)$$ 이 성립하고, $c(n)$ 은 정수입니다. 따라서 $n$ 의 서로 다른 홀수 소인수가 $r$ 개 라면 $2^r \mid \phi(n)$ 입니다.