오일러 피 공식 유도

https://m.blog.naver.com/yyhjin12/222864062441

오일러 피 함수(Euler's phi function)

 

백준 11689번 문제를 풀던 중, 오일러 피 공식이라는 것을 알게 됐다.

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

오일러 피 공식이란, 어떤 수 N이 주어졌을 때, N과 서로소인 수의 개수를 찾는 공식을 얘기한다. 

자세한 공식에 대한 설명은 위 블로그를 참조하길 바란다. 

 

그런데 이제 나는 어떻게, 저 공식이 나왔는지 그 유도 과정이 궁금하여 여기 블로그에 정리를 추가적으로 해본다. 

 

결론부터 말하면, 포함 배제의 원리를 전개식으로 만든 결과가 위 공식인 것이다. 

 

예시를 통해 이해해보자. 

만약 어떤 수 A의 소인수가 2와 3이라고 해보자. 

 

그리고 우리가 구해야할 것은, 소인수이지만, 먼저 반대로 A의 소인수가 아닌 수의 비율을 구하려면 어떻게 해야할까? 2의 배수 또는 3의 배수를 구하면 된다. 그리고 이것은 자명하게도, 포함/배제의 원리에 따라,

1/2 + 1/3 - 1/2*3 이 된다. 

이걸 수식으로 정리해보면, a

1 - (1-1/2)(1-1/3) 이 된다. 

그럼 A와 소인수인 수의 비율은 자연스레 (1-1/2)(1-1/3) 이 된다. 

 

이 외에 소인수가 3개, 4개...인 경우에도 똑같은 전개식이 나온다. (실제로 해봄으로써 알 수 있다.) 

 

난 이 과정에서 포함 배제의 원리를 4개째 적용하는 것부터 힘들었는데.. 

아래와 같이 하면 할 수 있다.

 

 

A와 소인수인 수의 비율을 구했으니, 실제 답은 

A*(소인수 비율) 이 됨을 알 수 있다.