問題#A017 ★☆☆☆
$n+1$ と $2n+3$ は互いに素であることを示せ。
《ポイント》
皆さんの大好きな公約数問題です(笑)。例えば問題が「$45$と$91$は互いに素であることを示せ。」だったら皆さんはどういう解答を作りますか？（自明といえば自明なのですが･･･）
一般に、公約数の問題（互いに素の証明も含む）では
「最大公約数を設定する」
というのが鉄則中の鉄則です。騙されたと思って$45$と$91$の最大公約数を$d$（$d$は正の整数）と置いてみましょう。すると$45$も$91$も$d$の倍数ですから、その差である$91-45=46$も$d$の倍数です（この理屈が分からない人は$45=dk$、$91=dl$とおいて差を取ってみて下さい。$46=d(l-k)$となって$46$も$d$の倍数になっていますよね？）。
$46$も$d$の倍数ですから$46$と$45$の差も$d$の倍数でなければなりません。したがって$1$は$d$の倍数となりますが、そのような正の整数$d$は$1$以外にあり得ません。よって、$45$と$91$の最大公約数は$1$、つまり$45$と$91$は互いに素、という結果を得ます。これが「ユークリッドの互除法」の仕組みでした（ユークリッドの互除法についてはコチラをご覧ください）。
これを一般の文字についてやるだけです。
《解答例》
$n+1$ と $2n+3$ の最大公約数を$d$（$d$は正の整数）と置くと、その差$$(2n+3)-(n+1)=n+2$$も$d$の倍数であり、これと$n+1$との差$$(n+2)-(n+1)=1$$も$d$の倍数となる。故に$d=1$であるから $n+1$ と $2n+3$ は互いに素である。
□
《コメント》
最大公約数を仮定してしまえば後は楽勝ですね。「ＡとＢが互いに素であることを示せ。」という問題は、よっぽどのことがない限りこの方法で片付けることができます。