[Algorithm] 오일러 파이(피) 함수 Euler's phi function

https://m.blog.naver.com/PostView.nhn?blogId=thqkdrhks22&logNo=150130493315&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

https://nuriwiki.net/wiki/index.php/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

오일러 피 함수

누리위키, 온 누리의 백과사전

오일러 피 함수(Euler's phi function) 또는 오일러 파이 함수 ϕ(n)$\varphi (n)$이란 어떤 자연수 n$n$보다 작거나 같은 자연수 중에서 n$n$과 서로소인 것의 개수를 나타내는 함수이다. 예를 들어, ϕ(8)=∣{1,3,5,7}∣=4$\varphi (8)=\mid \{1,3,5,7\}\mid =4$이다. 이것을 수식으로 표현하면 다음과 같다: 

ϕ(n)=∣{a∈ℕ|1≤a≤n,(a,n)=1}∣.$$\varphi (n)=\mid \{a\in N|1\le a\le n,(a,n)=1\}\mid .$$

성질[편집]

p$p$는 소수라고 하자.

• ϕ(p)=p−1$\varphi (p)=p-1$.
  • 역으로, ϕ(n)=n−1$\varphi (n)=n-1$이라면, n$n$은 소수이다.
• ϕ(pa)=pa−pa−1$\varphi (p^a)=p^a-p^{a-1}$.
• (m,n)=1$(m,n)=1$이라면, ϕ(mn)=ϕ(m)ϕ(n)$\varphi (mn)=\varphi (m)\varphi (n)$이다. (오일러 피 함수는 곱셈적 함수이다.)

참고문제: https://www.acmicpc.net/problem/4355