오일러 파이 함수

 

 

오늘은 오일러 파이 함수에 대해 알아보겠습니다.

사실 오일러 파이 함수는 그냥 고등학교 수학에서는 나오지 않습니다.

하지만 편하게 쓰기 좋은 내용이니 알아두면 사용할 일이 있을 것입니다.

 

1. 오일러 파이 함수란?

먼저 기호는 아래와 같습니다.

$ \phi \left ( n \right )$

$ 1$~$n$까지 수 중에서 $n$과 서로소인 수의 개수를 나타냅니다.

예를 들어 $ \phi \left ( 6 \right )=2$입니다.

6과 서로소인 수는 1,5 두개이기 때문입니다.

 

2. 성질들

오일러파이 함수는 여러 성질을 가지고 있습니다.

---

1. 소수 $p$에 대해 $ \phi \left ( p \right ) = p-1$

이 성질은 설명이 필요없을 정도로 당연합니다.

소수는 자기자신을 제외한 수와는 모두 서로소니까요.

---

2. 소수 $p$에 대해 $ \phi \left ( p^k \right ) = p^{k-1} (p-1)$

사실 1번 성질이 2번 성질의 특수한 경우입니다.

$p^k$와 서로소이려면 $p$를 인수로 가지고 있으면 안됩니다.

계산을 위해서 $p^k$까지의 수 중에서 $p$의 배수의 개수를 알아야합니다.

 

$p, 2p, 3p, ... ,p^k$까지 총 $p^{k-1}$개의 $p$의 배수가 있는 것을 알 수 있습니다.

따라서 전체에서 배수의 개수를 빼면

$p^k - p^{k-1} = p^{k-1} (p-1) $이 되어 2번 식이 나오게 됩니다.

---

3. 서로소인 두 수$m,n$에 대해 $  \phi \left ( mn \right )= \phi \left ( m \right ) \phi \left ( n \right )$

좌변이 왜 우변과 같은지를 알아보기 위해 $1$~$mn$까지의 수를 적었다고 생각해봅시다.

이 중에서 $mn$과 서로소인 수가 몇개인지를 파악하는 방식으로 설명하겠습니다.

여기서 임의의 행에 대해 생각해보겠습니다.

여기서 경우를 2가지로 나눌 수 있습니다.

 

1) $r$ 과 $m$이 서로소가 아니다.

2) $r$ 과 $m$이 서로소이다.

 

1)번의 경우

$r$째 행의 모든 수들은 $m$과 서로소가 아닙니다.

$m$이 $r$과 서로소가 아니면

당연히 $m$의 배수도 $r$과 서로소가 아니고 이에 $r$을 더해도 서로소가 아니기 때문입니다.

 

2)번의 경우

$r$째 행의 임의의 두 수를 생각해봅니다.

각각 $im+r , jm+r$이라고 가정하겠습니다.

 

만약 이 두 수가 $n$으로 나눈 나머지가 같다면

$im, jm$ 두 수도 $n$으로 나눈 나머지가 같습니다.

 

여기서 문제에서 제시한 $m,n$이 서로소라는 조건때문에

$im,jm$을 $n$으로 나눈 나머지가 같다면 $i,j$를 $n$으로 나눈 나머지도 같습니다.

 

그런데 $i,j$는 $n$보다 작기 때문에

$n$보다 작으면서 $n$으로 나눈 나머지가 같으려면 $i=j$여야 합니다.

하지만 임의의 두 수를 가져온 것이므로 $i,j$는 달라야합니다.

 

그래서 처음 가정인 

"두 수가 $n$으로 나눈 나머지가 같다면"은 틀렸습니다.

결국 $r$째 행의 임의의 두 수는 $n$으로 나눈 나머지가 다르다는 것입니다.

 

$r$째 행은 정확히 $n$개의 숫자가 있으므로 이 안에서 나머지가 서로 다 다르려면

$n$으로 나눈 나머지는 $0,1,2,...,n-1$ 이 각각 한번 씩 나와야 합니다.

이 행에는 $n$과 서로소인 수가 $ \phi \left ( n \right )$개 있을 것입니다.

 

또 $r,m$이 서로소이기 때문에

이 행의 모든 원소도 $m$과 서로소 입니다.

 

$m$과 서로소이고, $n$과 서로소이면 $mn$과도 서로소이므로

이 행에서 $mn$과 서로소인 수의 개수는 $n$과 서로소인 수의 개수와 같아 $ \phi \left ( n \right )$입니다.

 

이런 행이 2)에서 얘기한 $m$과 서로소인 $r$의 개수만큼 있으므로

이는 $ \phi \left ( m\right )$이 되고 

$  \phi \left ( mn \right )= \phi \left ( m \right ) \phi \left ( n \right )$입니다.

 

---

4. 소인수를 통한 오일러파이 계산

이제 가장 많이 쓰이는 성질입니다.

오일러 파이를 구할 때 일일히 세지 않고 계산할 수 있는 방법입니다.

 

소수 $p_1, p_2, p_3 ...$가 있다고 하면

$n={p_1}^{k_1}{p_2}^{k_2}{p_3}^{k_3}...$처럼 소인수분해 될 수 있습니다.

$  \phi \left ( n \right )= \phi \left ( p_1^{k_1} p_2^{k_2} p_3^{k_3} ...\right )$

3번 성질을 사용해 

$ = \phi \left ( p_1^{k_1} \right ) \phi \left ( p_2^{k_2} \right ) \phi \left( p_3^{k_3} \right) ...$

 

2번 성질을 사용하면

 $= p_1 ^{k_1} (1- \frac{1}{p_1})p_2 ^{k_2} (1- \frac{1}{p_2})p_3 ^{k_3} (1- \frac{1}{p_3})...$

$ =n (1-\frac{1}{p_1})(1-\frac{1}{p_1})(1-\frac{1}{p_3})$

 

식으로 보면 복잡해 보일 수 있지만

예시를 보면 쉽게 사용할 수 있는 공식이라는것을 알 수 있습니다.

 

$20$ 은 소인수로 $2,5$를 가지므로

 $  \phi \left (20 \right )=20 \frac{1}{2} \frac{4}{5}=8$처럼

1~20사이 수 중 20과 서로소인 수를 일일히 세지 않고도 쉽게 계산할 수 있습니다.