Euler's Phi (오일러 파이 함수)

개념 및 정의

오일러 파이 함수의 정의는 아래와 같습니다.

---

Phi function

즉, 이를 해석해 보면 양의 정수 n의 오일러 파이 함수는, 1부터 n까지의 정수 가운데 n과 서로소인 것들의 개수 입니다.

 

---

성질

1. 두 정수 m과 n이 서로소인 경우

n의 서로소 개수 곱과 m의 서로소 개수 곱은 n*m의 서로소 개수입니다.

 

2. 정수 p가 소수인 경우

소수 p의 서로소는 1을 제외한 모든 수입니다.

3. 소수 p의 거듭제곱인 경우

 

1~3을 종합한 결론  

위 성질들을 통해 소인수를 이용한 오일러 파이 함수를 아래와 같이 구할 수 있습니다.  그리고 아래 함수를 오일러 곱 공식이라고 합니다. 

---

예를 들어, 20의 소인수는 2와 5 이므로, ∅(20) 은 20(1-1/2)(1-1/5) = 8로 구할 할 수 있습니다.

 

---

증명

오일러 곱 공식을 증명해 보면, 아래와 같습니다.

---

오일러 곱 공식 증명

 

따라서, 어떤 양의 정수의 소인수들을 안다면, 오일러 파이 함수를 빠르게 구할 수 있습니다.  

---

오일러 정리

오일러의 정리는 다음과 같습니다.

 n이 양의 정수이고, gcd(a, n) = 1이면,

합동식(≡)은 간단히 말해 a ≡ b (mod n) 일 때, "a를 n으로 나눈 나머지가 b"라는 문장을 수식으로 표현한 것입니다.

---

위 성질을 이용하면 복잡한 계산도 간단하게 해결할 수 있습니다.

예를 들어, 2009^1002을 100으로 나눈 나머지를 구하라고 하면 풀이는 아래와 같습니다. (접은 글)

 

[풀이]

100의 소인수: 2, 5 
∅(100) = 100(1-1/2)(1-1/5) = 40이고, 2009와 100은 서로소입니다. 따라서 2009^40 ≡ 1 (mod 100)입니다.
따라서, 2009^1002 = 2009^(25*40 + 2) ≡ 2009^2 (mod 100) ≡ 9^2 (mod 100) = 81 (mod 100) 

---

코드

아래 코드는 백준  4355번 문제(https://www.acmicpc.net/problem/4355)를 바탕으로 작성되었습니다.

---

#include<stdio.h>

int Euler(int n) {
	double ans = n;

	for (int i = 2; i*i<= n; i++) {
		if (n % i == 0) { // i: 소수
			ans = ans - ans / i;
			while (n % i == 0) {		
				n /= i; //n을 그 소수로 나눈 후 다시 반복
			}
		}
	}

	if (n != 1) // n이 소수인 경우
		ans = ans - ans / n;
	return (int)ans;
}

int main() {
	int n;
	
	while (1) {
		scanf("%d", &n);
		if (n == 0) break;
		
		printf("%d\n", n==1? 0: Euler(n));
	}

}

---

관련문제

https://www.acmicpc.net/problem/4355

4355번: 서로소

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

 

---

 

참고

https://namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D

https://namu.wiki/w/%EC%98%A4%EC%9D%BC%EB%9F%AC%20%EC%A0%95%EB%A6%AC

https://blog.naver.com/thqkdrhks22/150130493315