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

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

Leonhard Euler

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

서로 소는 두개의 수에 대한 소인수 분해하여 공통 인자가 없는 경우입니다. 즉, 최대 공약수가 1이라는 뜻입니다.
$\phi (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)$는 서로 다른 세소수의 곱
이 때, $\phi (x)+\phi (y)+\phi (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이어서는 안 된다.
$\phi (q^2)=q(q-1)$이므로 최소값을 가지기 위해서는 q는 3보다 큰 소수 중에 $\sigma (q^2)=q^2+q+1$이 소수여야 한다. 이를 만족하는 최소 소수는 5가 된다. ( $\sigma (5^2)=5^2+5+1=31$ )
따라서 $\phi (4)+\phi (2)+\phi (25)=2+1+20=23$이 최소값이 된다.