互いに素な自然数の性質とその証明

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