【2021京都府立大学・生命環境】
（１） \(31\) が素数であることを、背理法を用いて証明せよ．
\(3\)、\(5\)、\(7\) が素数であることは用いて良い．
（２） \(_{31}C_{r}\) ( \(r=1,2,\cdots,30\) ) を \(31\) で割った余りは \(0\) であることを、背理法を用いて証明せよ．
（３） すべての自然数 \(n\) に対して \(n^{31}-n\) を \(31\) で割った余りは \(0\) であることを、数学的帰納法を用いて証明せよ．
考え方
背理法とは？
ある主張Ａを証明するのに、Ａでないという前提からは矛盾が生ずると示すことで行う証明法
解答の流れについて
「ある主張Aが正しい」ことを示せ、と言う問題に対して
Step1：「主張Aは間違っている(結論を否定)」と仮定する
Step2：主張Aが間違っている前提で話を進め、矛盾を導く
Step3：主張Aが間違っていると仮定したことがダメ！つまり主張Aは正しい！
数学的帰納法
\(n = 1 , 2 , 3 , \cdots\)(自然数) に対しての証明
⇒ 数学的帰納法を利用
(ⅰ) \(n = 1\) のとき命題が成立することを示す
(ⅱ) \(n = k\) のとき命題が成立すると仮定し、\(n=k+1\) のとき命題が成立することを示す
二項定理
\(\boldsymbol{(a+b)^{n}=_{n}\hspace{-1.4mm}{\rm C}_{0}a^{n}+_{n}\hspace{-1.4mm}{\rm C}_{1}a^{n-1}b+_{n}\hspace{-1.4mm}{\rm C}_{2}a^{n-2}b^{2}+\cdots+_{n}\hspace{-1.4mm}{\rm C}_{n-1}ab^{n-1}+_{n}\hspace{-1.4mm}{\rm C}_{n}b^{n}}\)
\(\boldsymbol{\displaystyle (a+b)^{n}=\sum_{k=0}^{n} \hspace{0mm} _{n}\hspace{-0.5mm}{\rm C}_{k}a^{n-k}b^{k}}\)
\(a=1 , b=x\) とすると、
（１）解答：背理法
\(31\) が素数でないと仮定する．
このとき、\(30\) 以下の素数 \(p\) と、\(30\) 以下の自然数 \(q\) を用いて
\(31=pq\) ・・・① とおける．
①より、\(31\) は奇数であるから、\(p\)、\(q\) はともに奇数となる．
よって、\(p\) は \(3≦p≦9\) を満たす素数となる．
つまり、 \(3\)、\(5\)、\(7\) のいずれかとなるが、
\(p=3\) のとき、\(q=\displaystyle\frac{31}{3}\)
\(p=5\) のとき、\(q=\displaystyle\frac{31}{5}\)
\(p=7\) のとき、\(q=\displaystyle\frac{31}{7}\)
はいずれも \(q\) は自然数とならない．つまり矛盾する．
したがって、\(31\) が素数である．
（２）解答：背理法
\(_{31}C_{r}\) ( \(r=1,2,\cdots,30\) ) を \(31\) で割った余りが \(n\) ( \(0<n≦30\) を満たす自然数 )であると仮定すると、\(0\) 以上の整数 \(m\) を用いて、
\(_{31}C_{r}=31m+n\) とおける．
ここで、\(_{31}C_{r}\)\(=\displaystyle\frac{31!}{(31-r)!r!}\) であるから、
\(\displaystyle\frac{31!}{(31-r)!r!}=31m+n\)
よって、\(31!=(31m+n)(31-r)!r!\)
\(31!=31m(31-r)!r!+n(31-r)!r!\)
\(31\left\{30!-m(31-r)!r!\right\}=n(31-r)!r!\) ・・・②
②の左辺は \(31\) の倍数、つまり左辺を \(31\) で割った余りは \(0\) となる．
また②の右辺は、 \(1≦r≦30\)、\(0<n≦30\)、\(31\) は素数であるから \(n(31-r)!r!\) は \(31\) を因数に持たないため矛盾する．
したがって、\(_{31}C_{r}\) ( \(r=1,2,\cdots,30\) ) を \(31\) で割った余りは \(0\) である．
（３）解答：数学的帰納法
( ⅰ ) \(n=1\) のとき
\(n^{31}-n=1^{31}-1=0\) であるから、\(n^{31}-n\) を \(31\) で割った余りは \(0\)
( ⅱ ) \(n=k\) のとき
\(k^{31}-k\) を \(31\) で割った余りが \(0\) ・・・③ であると仮定する．
\(n=k+1\) のとき
\((k+1)^{31}-(k+1)\)
\(=(_{31}C_{0}+_{31}C_{1}k+_{31}C_{2}k^2+\cdots+_{31}C_{30}k^{30}+_{31}C_{31}k^{31})-(k+1)\)
\(=(1+_{31}C_{1}k+_{31}C_{2}k^2+\cdots+_{31}C_{30}k^{30}+k^{31})-(k+1)\)
\(=(_{31}C_{1}k+_{31}C_{2}k^2+\cdots+_{31}C_{30}k^{30})+(k^{31}-k)\)
（２）、③より、
\(_{31}C_{1}k\)、\(_{31}C_{2}k^2\)、\(\cdots\)、\(_{31}C_{30}k^{30}\)、\(k^{31}-k\) はそれぞれ \(31\) で割った余りは \(0\) となるため、\((k+1)^{31}-(k+1)\) を \(31\) で割った余りは \(0\) である．
( ⅰ )、( ⅱ )より、すべての自然数 \(n\) について、\(n^{31}-n\) を \(31\) で割った余りは \(0\) となる．
コメント