오일러 피(파이) 함수

* 오일러 피 함수(Euler phi function, )

  서로소 개수를 파악할 때 포함-배제의 원칙을 사용해도 되지만, 더욱 간단한 방법이 있습니다. 바로 오일러 피 함수의 특징을 이용하는 것입니다.

  오일러 피 함수의 정의는 다음과 같습니다.

  =n보다 작으면서 n과 서로소인 수의 개수

  

  * 성질

  명제 1) 오일러 피 함수는 곱셈적 함수(Multiplicative function)이다. 즉 gcd(m, n)=1이면 이다.

  증명) m X n 테이블이 있다고 해봅시다. 1부터 nm까지 수로 테이블을 열 순서로 채워서 아래처럼 만들어봅시다.

  이 테이블에서 r행에 있는 모든 원소를 가져오면 다음과 같은 형태를 띄게됩니다.

  d=gcd(r, m)이라고 정의한다면 두 가지 경우가 나옵니다.

  1. d > 1

  d > 1인 경우엔 r과 m이 서로소가 아님을 알 수 있고, 여기서 r행의 모든 원소 km+r 형태를 띄는 수는 nm과 서로소가 아니게 됩니다. 

  2. d = 1

  d = 1인 경우엔 r과 m이 서로소임을 알 수 있고, r행의 모든 원소 km+r 형태를 띄는 수가 nm과 서로소가 될 수 있는 후보가 됩니다. 이 때 이 후보의 수는 가 됩니다.

 행 m에 대해서 계산했으니, 열 n에 대해서 똑같이 계산하면 정답 후보군이 개 나오는 것을 알 수 있습니다. 정답 후보군을 테이블에서 정리해보면 총 개임을 알 수 있고 이는 곧 mn에 대한 서로소의 개수이기 때문에 로 증명이 가능합니다.

명제 2) 소수 p에 대해  이다.

증명) 의 서로소가 아니기 위해서는 그 수는 p의 배수임은 명확하게 보다 작으면서 p의 배수인 것의 개수는 개 입니다.

명제 3) n > 1인 정수 n에 대해 인 prime-power factorization이라면 

 이다.

증명) 명제 2)에 의해

 임을 알 수 있고 이를 정리하면 명제가 참임을 알 수 있다.

  

* 오일러 피 함수만을 사용하여 풀 수 있는 문제

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

- 오일러 프로젝트(https://projecteuler.net/)에 오일러 피 함수에 관한 문제가 많습니다. 대표적으로 69, 70번 문제가 있습니다. 다른 문제도 많으니 한 번 해보시길..