[Algorithm] 오일러 피 함수(Euler's phi function) | 서로소인 자연수의 개수 구하기 | Python

오일러 피 함수(Euler's phi function, ϕ)은 임의의 양의 정수 n과 서로소인 자연수의 개수를 구하는 함수이다.

 

---

 

1. n이 소수일 때

 

n이 소수일 때 ϕ(n)은 항상 (n-1)의 값을 가진다. 왜냐하면 소수는 모든 자연수와 서로소이기 때문이다.

 

$$ n = ab (a, b \in N, a<b) \neq 1 $$

$$ a = 1 \land b > 1 $$

$$ \phi (n) = n-1 $$

 

2. n이 소수의 거듭제곱일 때

 

n이 소수 p의 거듭제곱일 때에, ϕ(n)은 다음과 같이 계산된다.

 

$$ n = p^{k} $$

$$ p = ab(a, b \in N, a<b) \neq 1 $$

$$ a = 1 \land b > 1 $$

$$ \phi (n) = p^{k-1} (p-1) $$

 

3. m과 n이 서로소일 때

 

m과 n이 서로소일 때, mn과의 서로소의 개수는 m과의 서로소의 개수와 n과의 서로소의 개수의 곱과 같다,

 

$$ m \perp n $$

$$ \phi (mn) = \phi (m) \phi (n) $$

 

---

 

오일러 피 함수를 사용하여 임의의 수 n과 서로소인 자연수들의 개수를 살펴보자.

 

$$ \phi (3) = 2 $$

$$ \phi (27) = 3^{3} = 3^{2} \cdot 2 = 18 $$

$$ \phi (990) = 2 \cdot 3^{2} \cdot 5 \cdot 11 = \phi (2) \phi (3^{2}) \phi (5) \phi (11) = 1 \cdot 6 \cdot 4 \cdot 10 = 240 $$

 

---

 

이를 파이썬으로 구현해 보자.

 

def factorization(x): 
    d = 2 
    factorization = []
    while d <= x: 
        if x % d == 0: 
            factorization.append(d)
            x = x / d 
        else: 
            d = d + 1
    return factorization
    
    
def euler_phi(n):
    primes = factorization(n)
    k = 1
    for p in set(primes):
        k *= p**(primes.count(p)-1) * (p-1)
    return k

 

조건 1번과 조건 2번에서의 식은 어떤 수의 0승은 항상 1이기에 같은 식이라고 볼 수 있다. 따라서 17번 줄로 일반화된다.

 

 

---

 

이 글을 쓰는 데 도움이 되었던 자료들:

 

https://rkdxowhd98.tistory.com/135

Algorithm in A..Z - Euler's phi (오일러 피 함수)

 

https://zoosso.tistory.com/243

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

 

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전