최대공약수 순서쌍 추론

[출제의도] 순열을 이용하여 경우의 수 추론하기 $40$ 이하의 서로 다른 두 자연수 $a$, $b$의 최대공약수가 $3$이므로 서로소인 두 자연수 $m$, $n$에 대하여 $a = 3 m$, $b = 3 n$이라 하면 $m$과 $n$은 $13$ 이하의 자연수이다. 순서쌍 $( a , b )$를 선택하는 경우는 ‘(ⅰ) 서로 다른 두 자연수 $m$, $n$을 선택하는 경우’에서 ‘(ⅱ) 서로 다른 두 자연수 $m$과 $n$이 서로소가 아닌 경우’를 제외하면 된다. (ⅰ)의 경우 : $13$개의 자연수에서 서로 다른 두 자연수 $m$, $n$을 선택하는 경우의 수는 ${} _{13} \mathit{\mathrm{P}} \mathit{\mathrm{_{2}}} =$$\left. {\square {156 _{} ^{}}} \right.$이다. (ⅱ)의 경우 : $m$과 $n$이 $2$의 배수인 경우의 수는 ${} _{6} \mathit{\mathrm{P}} \mathit{\mathrm{_{2}}}$이고, $m$과 $n$이 $3$의 배수인 경우의 수는 ${} _{4} \mathrm{P} \mathit{\mathrm{_{2}}}$이고, $m$과 $n$이 $5$의 배수인 경우의 수는 ${} _{2} \mathrm{P} \mathit{\mathrm{_{2}}}$이다. 이 때, $2$와 $3$의 공배수인 $\left. {\square {6 _{} ^{}}} \right.$의 배수로 이루어진 순서쌍 $( 6 , 12 )$, $( 12 , 6 )$은 중복되므로 제외한다. 서로 다른 두 자연수 $m$과 $n$이 서로소가 아닌 경우의 수는 ${} _{6} \mathrm{P} _{2} + _{4} \mathrm{P} _{2} + _{2} \mathrm{P} _{2} - 2 =$$\left. {\square {42 _{} ^{}}} \right.$이다. 따라서 $40$ 이하의 서로 다른 두 자연수 $a$, $b$의 최대공약수가 $3$인 $a$, $b$의 모든 순서쌍 $( a , b )$의 개수는 $\left. {\square {156 _{} ^{}}} \right. - \left. {\square {42 _{} ^{}}} \right.$이다. $p = 156$, $q = 6$, $r = 42$이므로 $p + q + r = 204$