오일러 피 함수의 정의

$\phi(x)$라고 쓰며 phi라고 읽는다.

$\phi(x)$는 x와 서로소이며 0≤k<x인 숫자의 집합 개수이다 이를 수식적으로 나타내면 다음과 같다.

$$ \phi(x) = \|\{k \in \mathbb{Z^+} : k < x\ and\ gcd (x,k) = 1\}\| $$

• $\mathbb{Z^+}$ : 양의 정수 범위
• ||집합|| : 집합의 개수
• $a\in b$ : a는 b 집합의 포함 관계
• gcd(x,k) = n : x,k의 최대공약수가 n

한마디로 이 오일러의 피 함수를 이용하여 x의 서로소 개수를 구하는 것이다

• $\phi(4) = 1,2,3\ 중\ 4와\ 서로소는\ 1,3 = 2$
• $\phi(7) = 1,2,3,4,5,6은\ 7과\ 모두\ 서로소이기에 = 6$

STEP 1 간단하게 구하기

간단하게 구하는것은 아주 쉽다.

1. 1~N까지 모두 N과 gcd해보며 그 값이 1인것을 찾으면 된다

import math

N = int(input())
count = 0
for i in range(1,N):
    if math.gcd(N,i) == 1:
        count+=1
print(count)

하지만 이러한 방법은 시간복잡도가 NlogN이며 1e10 이상의 값도 다루는 정수론에 적합하진 않다.

STEP 2 오일러 피 함수 성질

성질 1. 오일러 피 함수는 곱셈적이다 ab = a * b로 나타낼 수 있다는것이다

$$ \phi(\alpha \beta) = \phi(\alpha)\phi(\beta) $$

성질 2. 소수 p의 거듭제곱에 대한 성질