連続する2つの自然数が互いに素であることを示せ.
(2)\ \ 連続する2つの正の奇数が互いに素であることを示せ. 互いに素な自然数の性質とその証明 \\
2つの整数$a,\ b$の最大公約数が1のとき,\ $a,\ b$は互いに素であるという.
最大公約数が1は,\ 1より大きい公約数をもたないという否定的表現に言い換えられる.
さらに,\ 素数の公約数をもたないと言い換えることもできる.
以上を踏まえると,\ 互いに素であることの証明として以下のような手法が考えられる.
$[1]$\ \ $2数の最大公約数をg}\,として,\ 直接g=1を示す.$
$[2]$\ \ $2数が\,1より大きい公約数g}\,をもつと仮定して矛盾を導く}(背理法}).}$
$[3]$\ \ $2数が素数の公約数p}\,をもつと仮定して矛盾を導く}(背理法}).連続する2つの自然数nとn+1の最大公約数をg}\,とする.$
(1)\ \ [1]}\ \ このとき,\ $n=ga,\ \ n+1=gb\ \ (a,\ b:互いに素な自然数)}とおける.$連続する2つの自然数nとn+1が公約数g\ (>1)をもつと仮定}する.$
(1)\ \ [1]}\ \ このとき,\ \ $n=ga,\ \ n+1=gb\ \ (a,\ b:自然数)}\ とおける.$
(1)\ \ [1]}\ \ $g(b-a)=1}$が導かれるが,\ $b-a$は整数なので,\ $g>1と矛盾}する.n,\ n+1は互いに素}である.$連続する2つの自然数nとn+1が素数の公約数pをもつと仮定}する.n=pa,\ \ n+1=pb\ \ (a,\ b:自然数)}\ とおける.$
(1)\ \ [1]}\ \ $p(b-a)=1}$が導かれるが,\ $b-a$は整数なので,\ $pが素数であることに矛盾}する.$
∴ n,\ n+1は互いに素}である.$}
2つの整数a,\ bが,\ 1より大きい,\ つまり2以上の公約数dをもつとする.
dはある素数pで割り切れるから,\ 公約数dをもつことは素数の公約数pをもつことである.
[1]}\ \ 自分で文字で設定し,\ 元からある文字を消去する}のが整数問題の極意であった.
\ \ 「\,A,\ Bの最大公約数がg\,」は,\ 「A=ga,\ B=gb\ (a,\ b:互いに素な整数)」と設定できる.
\ \ nを消去すると,\ (文字式)×(文字式)=(具体的な整数)の形に変形できる.
\ \ 最大公約数は必ず正の整数}であることも考慮して,\ g=1が確定する.
[2]}\ \ gは最大公約数ではないから,\ a,\ bは互いに素とは限らない}ことに注意する.
\ \ どちらにせよ,\ 本問は互いに素という条件を使わずとも証明できる.
[3]}\ \ 素数p≧2}より,\ p(b-a)=1は矛盾である.
連続する2つの正の奇数2n-1と2n+1の最大公約数をg\,}とする.$
(1)\ \ [1]}\ \ このとき,\ $2n-1=ga,\ \ 2n+1=gb\ \ (a,\ b:互いに素な正の奇数)}とおける.$ g=1},\ \ b-a=2$
∴ n,\ n+1は互いに素}である.$}連続する2つの正の奇数2n-1と2n+1が公約数g\ (>1)をもつと仮定}する.$
(1)\ \ [1]}\ \ このとき,\ \ $2n-1=ga,\ \ 2n+1=gb\ \ (a,\ b:正の奇数)}\ とおける.$
(1)\ \ [1]}\ \ $g(b-a)=2}$が導かれるが,\ $b-aは偶数なので,\
∴ n,\ n+1は互いに素}である.連続する2つの正の奇数2n-1と2n+1が奇素数の公約数pをもつと仮定}する.$
(1)\ \ [1]}\ \ このとき,\ \ $2n-1=pa,\ \ 2n+1=pb\ \ (a,\ b:正の奇数)}\ とおける.$
(1)\ \ [1]}\ \ $p(b-a)=2}$が導かれるが,\ $b-a$は整数なので$pが奇素数であることに矛盾}する.
[1]\ \ a,\ bを奇数と設定}しておく必要があることに注意する.
\ \ その結果,\ b-aが偶数となり,\ g=1が確定する.
[3]\ \ 奇素数p≧3}より,\ p(b-a)=2は矛盾である.
2つの自然数m,\ nに対し,\ 次が成立することを示せ.$
(1)\ \ $「\,m,\ nが互いに素」ならば「\,m+nとmnが互いに素」$
(2)\ \ $「\,m+nとmnが互いに素」ならば「\,m,\ nは互いに素」$
(3)\ \ $「\,m,\ nが互いに素」ならば「\,m^2\,とn^2\,が互いに素」$ \\
m+nとmnが素数の公約数pをもつと仮定}する.$
\ \ このとき,\ \ $m+n=pa,\ \ mn=pb\ \ (a,\ b:整数)}\ とおける.$
\ \ $mn=pbより,\ mまたはnは素数pの倍数}である.$ [\,ユークリッドの補題}\,]}
\ \ $mがpの倍数}のとき,\ m=pk\ (k:整数)}\ とおける.$
\ \ $このとき n=pa-m=pa-pk=p(a-k)$
\ \ $a-kは整数であるから,\ nもpの倍数}である.$
\ \ $これは,\ m,\ nが互いに素であることと矛盾}する.$
\ \ $nがpの倍数}のとき,\ 同様にmもpの倍数}となり,\ 矛盾する.$
∴ m+nとmnは互いに素}である.$}mとnが素数の公約数pをもつと仮定}とする.$
\ \ このとき,\ $m=pa,\ \ n=pb\ \ (a,\ b:整数)}とおける.$
\ \ $m+n=pa+pb=p(a+b), mn=pa･ pb=p^2ab}$
\ \ $よって,\ m+nとmnは素数pを公約数にもつ.$
\ \ $これは,\ m+n,\ mnが互いに素であることと矛盾}する.$
∴ m,\ nは互いに素}である.$}m^2\,とn^2\,が素数の公約数pをもつと仮定}する.$
\ \ このとき,\ \ $m^2=pa,\ \ n^2=pb\ \ (a,\ b:整数)}\ とおける.$
\ \ よって,\ $m,\ nはいずれも素数pの倍数}である.$
\ \ これは,\ $m,\ nが互いに素であることと矛盾}する.$
∴ m^2\,とn^2\,は互いに素}である.$
前問では,\ 素数の性質を利用せずとも証明できた.
しかし,\ 本問では以下の素数に関する定理を利用しなければ行き詰まる.
「\,mnが素数pの倍数」ならば「\,mまたはnが素数pの倍数」 (ユークリッドの補題)}
特にm=nとすると 「\,n^2\,が素数pの倍数」ならば「\,nが素数pの倍数」 (*)}
一見当たり前に思えるが,\ これらはpが素数だからこそ成り立つ定理であることに注意してほしい.
例えば,\ 「\,mnが6の倍数」ならば「\,mまたはnが6の倍数」は成り立たない(m=2,\ n=3).
また,\ 「\,n^2\,が4の倍数」ならば「\,nが4の倍数」も成り立たない(n=2).
本問はこの素数ならではの性質を利用するため,\ 素数の公約数pをもつと仮定する方法で証明する.
この証明方法は,\ 素数の性質を利用できる分,\ 他の証明方法よりも汎用性が高いといえる.
なお,\ ユークリッドの補題は記述試験で無断使用してもよい.
ユークリッドの補題によりmまたはnがpの倍数とわかるから,\ 各場合に分けて考える.
日本語「\,mがpの倍数」を数式「\,m=pk\ (k:整数)」に変換し,\ 元からある文字mを消去する.
さらに,\ 共通因数をもつ部分をまとめて共通因数をくくり出すことにより,\ nもpの倍数とわかる.
m,\ nが素数pを公約数としてもつことになり,\ m,\ nが互いに素であることに矛盾する.
nがpの倍数の場合も同様なので,\ 簡潔な記述で済ませておけばよい.
(2)\ \ 素数条件が必須ではなく,\ 最大公約数gをもつと仮定しても同様である.
(3)\ \ pは素数であるから,\ m^2=pa,\ n^2=pbより,\ m,\ nがpの倍数といえる.
以下の結果は記憶に値するが,\ 記述試験で無断使用してよいかはかなり微妙である.
簡潔でもよいので証明を書き,\ リスクを避けることを推奨する.
[\,A\,] $連続する2つの自然数n,\ n+1は互いに素である$
[\,B\,] $m,\ nが互いに素}\ ⇔\ m+n,\ mnが互いに素$
[\,C\,] $m,\ nが互いに素}\ ⇔\ m^2,\ n^2\,が互いに素$
