서로소의 개수 2 (오일러 파이 함수)

 

 

 

서로소의 개수2

자연수 \( n \) 이하 \( n \)과 서로소인 자연수의 개수를 구하는 아이디어는 지난 포스트에 언급하였다.

 

2024.06.01 - [수학] - 서로소의 개수

서로소의 개수

 

 

 

이번에는 이것을 쉽게 구하는 오일러 파이 함수를 소개한다.

 

자연수 \( n \)을 다음과 같이 소인수분해 하면,

\( n=p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_r^{a_r} \; \; ( p_i는 \, 소수 ) \)

일 때,

 

\( \phi(n)=n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right) \cdots\left(1-\dfrac{1}{p_r}\right) \)

 

이 함수를 차근차근 유도해 보자.

 

1. 먼저 자연수 \( n= p^a \) 즉, 하나의 소인수를 가지는 수라고 생각해 보자.

 

\( n \) 개의 자연수 중에서 \( p \)의 배수만 빼주면, 서로소의 개수를 셀 수 있다.

 

\( p \)의 배수의 개수는 \( \dfrac{n}{p}=p^{a-1} \) 개 이다.

 

\( \phi\left(p^a\right)=p^a-p^{a-1}=p^a\left(1-\dfrac{1}{p}\right)=n\left(1-\dfrac{1}{p}\right) \)

 

임을 알 수 있다.

 

2. 서로소인 두 수 \( m \), \( n \)에 대하여,

 

\( \phi(m n)=\phi(m) \phi(n) \)

 

이 성립하는지 알아보자.

 

여기에서는 정교한 증명은 하지 않고, 성립할 수 밖에 없는 이유를 보여주려고 한다.

 

\( m=p^a, \; n= q^b \) 라고 하자. ( \( p \), \( q \)는 소수 \( a \), \( b \)는 자연수 )

 

\( \phi(mn) = mn \left(1 - \dfrac{1}{p} \right) \left(1- \dfrac{1}{q} \right) = m \left(1 - \dfrac{1}{p} \right) \times n \left(1- \dfrac{1}{q} \right) = \phi(m) \phi(n) \)

 

앗, 너무 간단한가? 수식의 오른쪽에서 왼쪽으로도 성립한다. 의심이 들면 이렇게 생각해 보자.

 

서로소인 두 수 \( m=p^a, \; n= q^b \)에서 \( mn \)이하 자연수에서 \( mn \)과 서로소인 수의 개수를 직접 세어보자.

 

( \( mn \) 이하 \( p \) 또는  \( q\)의 배수 갯수 ) = ( \( p \)의 배수 갯수) + ( \( q \)의 배수 갯수) - ( \( p \), \( q \)의 공배수 갯수)

 

\( = \dfrac{mn}{ p} + \dfrac{mn}{q} - \dfrac{mn}{pq} \)

 

이것을 \( mn \)에서 빼주면 

 

\( \phi(mn) = mn - \left( \dfrac{mn}{ p} + \dfrac{mn}{q} - \dfrac{mn}{pq} \right)  \)

\( \qquad = mn \left( 1 - \dfrac{1}{p} - \dfrac{1}{q} +  \dfrac{1}{pq} \right) \)

 

괄호 안을 인수분해 하면

 

\( \phi(mn) = mn \left(1 - \dfrac{1}{p} \right) \left(1- \dfrac{1}{q} \right) = \phi (m) \phi(n) \)