오일러 피 함수

정의

오일러 피 함수(Euler phi function) $\varphi(n)$는 정수론에서 정의되는 함수 중의 하나로, 다음과 같다.

즉, $\varphi(n)$은 1보다 크거나 같고 $n$보다 작은 정수, 즉 $n$ 이하 자연수들 중에서 $n$과 서로소인 수의 개수이다.

$n$의 값에 따른 $\varphi(n)$의 값을 일부 나타내면 다음과 같다.

$n$	$\varphi(n)$
1	1
2	1
3	2
4	2
5	4
10	4
20	8
50	20

---

성질

오일러 피 함수가 만족하는 성질은 다음과 같다.

• 자연수 $a, b$에 대해 $\gcd(a, b) = 1$이라면, $\varphi(ab) = \varphi(a)\varphi(b)$.
• 임의의 자연수 $k$와 소수 $p$에 대해, $\varphi(p) = p-1,\ \varphi(p^k) = p^{k-1}(p-1)$
• 자연수 $m, n$에 대해 $m | n$이면, $\varphi(m) | \varphi(n)$도 성립한다.

---

오일러 곱 공식

여기에서 다음과 같은 오일러 곱 공식(Euler's product formula)를 유도 가능하다.

여기서, $\prod_{p | n}$은 $n$을 나누어 떨어지게 만드는 소수 $p$에 대한 곱이다.

오일러 곱 공식 증명

자연수 $n$은 소수들로 소인수분해 가능하다. 즉, 다음과 같이 쓸 수 있다.

이를 오일러 피 함수에 대입하면 다음과 같다.

증명이 완료되었다.

---

오일러 피 함수 구현

오일러 피 함수는 위의 성질들을 이용해 다음과 같이 c++ 코드로 구현 가능하다.

#include <bits/stdc++.h>

typedef long long ll;

ll phi(ll k) {
    ll result = k;
    for (ll i = 2; i*i <= k; i++) {
        if (k % i == 0) {
            result -= result / i;
            while (k % i == 0) {
                k /= i;
            }
        }
    }
    if (k > 1) {
        result -= result / k;
    }
    return result;
}