\(\varphi(x)+\varphi(y)+\varphi(z)\)의 최소값 문제

문제 출처는 중학 수학 문제지입니다. 사실 그 때, 문제 풀었을 때, 문제지 답지가 틀렸었던 문제였습니다. 문제 출제하신 분이 좀 착각을 했었던 듯 합니다. 사실 중학 수학 문제에 정수론에서 사용되는 것들을 사용하는 것은 바람직하지 않습니다.

Leonhard Euler

정수론과 관련해서 용어를 설명드리겠습니다.

서로 소는 두개의 수에 대한 소인수 분해하여 공통 인자가 없는 경우입니다. 즉, 최대 공약수가 1이라는 뜻입니다.
\(\varphi(x)\)는 x보다 작은 자연수 중에서 x와 서로 소인 수의 개수를 뜻하며, 오일러의 수(Euler's totient)라고 합니다.
\( (a, b) = g \) 형태의 표현법은 a와 b 수의 최대 공약수가 g라는 표현입니다.
\( \sigma (x) \) 는 x의 약수의 합을 말합니다.

 

문제)

1보다 큰 자연수 \(x, y, z\)가 서로 다른 소수 \(p, q\)에 대하여 다음이 성립할 때,
조건 (1) \( (x+y+z, p \times q) = 1\)
조건 (2) \( x \times y \times z = p^3 \times q^2 \)
조건 (3) \( \sigma (x) \times \sigma (y) \times \sigma (z) \)는 서로 다른 세소수의 곱
이 때, \(\varphi(x)+\varphi(y)+\varphi(z)\)의 최소값은 얼마인가?

 

풀이)

조건 (1), (2), (3)에 의해 \(x, y, z\) 세 수는 \( p^2 , p, q^2 \)이 되어야 한다.
\(x, y, z\) 세 수는 1보다 큰 자연수이므로
조건 (3)에 의해 \( \sigma (x), \sigma (y), \sigma (z) \)는 서로 다른 소수여야 한다.
소수 p에 대하여 \( \sigma (p) = p + 1 \) 이므로, \( p + 1 \)이 소수가 되기 위해서 p는 유일한 짝수 소수인 2로 유일하다.
조건 (1)을 만족하기 위해서는 \( 2^2 + 2 + q^2 = 6 + q^2 \)이 되므로,
q는 \( (6, q^2) = 1 \) 이어야 하므로, q는 3이어서는 안 된다.
\( \varphi (q^2) = q(q-1) \)이므로 최소값을 가지기 위해서는 q는 3보다 큰 소수 중에 \(\sigma (q^2) = q^2 + q + 1\)이 소수여야 한다. 이를 만족하는 최소 소수는 5가 된다. ( \( \sigma (5^2) = 5^2 + 5 + 1 = 31 \) )
따라서 \( \varphi(4) + \varphi(2) + \varphi(25) = 2 + 1 + 20 = 23 \)이 최소값이 된다.