서로소의 개수 3 - 오일러 파이 함수를 이용한 몇가지 예제 풀이

 

서로소의 개수 3

지난 시간에는 서로소의 개수를 구하는 오일러 파이 함수 \( \phi(n) \)를 유도해 보았다.

 

2024.06.03 - [수학] - 서로소의 개수 2 (오일러 파이 함수)

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

 

 

 \( \phi(n) \)을 이용하여 몇가지  문제를 해결해 보자

 

<문제>

750이하 자연수 중에서 246과 서로소인 수의 총합을 구하시오.

 

<해결 전략>

1. 246이하 자연수에서 246과 서로소인 수의 개수를 구한다.

2. 750이하 자연수에서 246과 서로소인 수의 개수를 구한다.

3. \( 738 = 246 \times 3 \)이므로 738이하 자연수에서 246과 서로소인 수의 총합을 구한다.

4. 738이상이고 750이하 자연수 중에서 246과 서로소인 수의 합을 구해 3에서 구한 총합과 더한다.

 

<풀이>

1. 246이하 자연수에서 246과 서로소인 수의 개수를 구한다.

\( 246 = 2 \times 3 \times 41 \) 이므로

\( \phi(246) = 246 \times \left( 1 - \dfrac{1}{2} \right) \left( 1 - \dfrac{1}{3} \right) \left( 1 - \dfrac{1}{41} \right) = 80 \)

 

2. 750이하 자연수에서 246과 서로소인 수의 개수를 구한다.

246보다 작은 자연수 \( k \)가 246과 서로소일 때,

\( 246 + k \), \( 246 \times 2 + k \), \( \cdots \)도 246과 서로소이다.

\( 750 = 246 \times 3 + 12 \) 이므로

(1에서 246까지 서로소 개수) = (247에서 492까지 서로소 개수) = (493에서 738까지 서로소 개수) = 80

또한 738+1, 738+5, 738+7, 738+11 도 246과 서로소이다.

따라서 750이하 자연수 중 246과 서로소인 수는 \( 80 \times 3 + 4 = 244 \) 개이다.

 

3. \( 738 = 246 \times 3 \)이므로 738이하 자연수에서 246과 서로소인 수의 총합을 구한다.

\( k \)가 246과 서로소일 때, \( 738 - k \)도 246과 서로소이다.

\( k \)와 \( 738 - k \) 두 수의 합은 738이고 738이하 246과 서로소인 수의 개수는 240이므로

738이하 자연수에서 246과 서로소인 수의 총합은

\( \dfrac{1}{2} \times 738 \times 240 = 88560 \)

 

4. 738이상이고 750이하 자연수 중에서 246과 서로소인 수의 합을 구해 3에서 구한 총합과 더한다.

738+1, 738+5, 738+7, 738+11 도 246과 서로소이다.

 

750이하 자연수 중에서 246과 서로소인 수의 총합은

\( 88560 + 739 + 743 + 745 + 749 = 91536 \)이다.