問題#A018 ★☆☆☆
すべての自然数$n$に対して$\dfrac{21n+4}{14n+3}$が既約分数であることを示せ。
《ポイント》
前問に引き続き公約数の問題です。分数が既約であるということは分子と分母が互いに素であるということです（確率の計算なんかで既約分数にしないまま答案を提出してペケ、なんていう経験をした人は少なくないでしょう）。本問は $21n+4$ と $14n+3$ が互いに素であることを示すだけですが、文字部分を消去するときに少し上手い工夫をします。
《解答例》
$21n+4$ と $14n+3$ の最大公約数を$d$（$d$は正の整数）と置くと、その差$$(21n+4)-(14n+3)=7n+1$$も$d$の倍数である。$14n+3$は$2$と互いに素であるから、$14n+3$と$2(7n+1)$の最大公約数は$d$のままである。故にその差$$(14n+3)-2(7n+1)=1$$も$d$の倍数である。したがって$d=1$を得るから、すべての自然数$n$に対して $21n+4$ と $14n+3$ は互いに素である。よってすべての自然数$n$に対して$\dfrac{21n+4}{14n+3}$が既約分数であることが示された。
□
《コメント》
この問題も最大公約数を仮定してしまえばあっさり片付きます。こんな問題が国際数学オリンピックで出題されたとは誰も思いませんよね･･･。
（出典：1959年第1回 IMO Problem 1）