スポンサーリンク

【2021京都府立大学・生命環境】n^31-nを31で割った余り|背理法・数学的帰納法

数学(大学入試問題)

【2021京都府立大学・生命環境】

(1) \(31\) が素数であることを、背理法を用いて証明せよ.

\(3\)、\(5\)、\(7\) が素数であることは用いて良い.

(2) \(_{31}C_{r}\) ( \(r=1,2,\cdots,30\) ) を \(31\) で割った余りは \(0\) であることを、背理法を用いて証明せよ.

(3) すべての自然数 \(n\) に対して \(n^{31}-n\) を \(31\) で割った余りは \(0\) であることを、数学的帰納法を用いて証明せよ.

考え方

背理法とは?

ある主張Aを証明するのに、Aでないという前提からは矛盾が生ずると示すことで行う証明法

解答の流れについて

「ある主張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\) とすると、

\(\boldsymbol{(1+x)^{n}=_{n}\hspace{-1.4mm}{\rm C}_{0}+_{n}\hspace{-1.4mm}{\rm C}_{1}x+_{n}\hspace{-1.4mm}{\rm C}_{2}x^{2}+\cdots+_{n}\hspace{-1.4mm}{\rm C}_{n-1}x^{n-1}+_{n}\hspace{-1.4mm}{\rm C}_{n}x^{n}}\)

(1)解答:背理法

\(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\) が素数である.

(2)解答:背理法

\(_{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\) である.

(3)解答:数学的帰納法

( ⅰ ) \(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)\)

(2)、③より、

\(_{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\) となる.

コメント

タイトルとURLをコピーしました