前回に引き続いて、魔法少女まどか☆マギカ数学。今回はほむらが指名された問題（上の動画2:13）。
問題は以下の通り。
問題：
pは素数、nは任意の自然数とします。
$(1+n)^p - n^p - 1$がpで割りきれることを証明してください。
解答（証明）：
二項定理($ (x+y)^a = \sum_{b=0}^a {_a\textrm{C}_b} x^b y^{a-b}$)を用いて、与式を以下のように変形します。
\begin{align*}
(1+n)^p & - n^p - 1 = \sum_{k=0}^p [ _p\textrm{C}_k n^k 1^{p-k} ] -n^p-1 \\
& = \left[1+pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}+n^p \right ] -n^p-1 \\
& =pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}
\end{align*}
ここで、$ n,n^2,n^3,\ldots ,n^{p-1}$は、すべて自然数です。
また、$ n,n^2,n^3,\ldots ,n^{p-1}$の各項の係数は、組み合わせの個数($ _p\mathrm{C}_k$)ですから、これも自然数です。式から、これらは公約数pをもっていることが分かります。
以上から、与式は[p]×[自然数]の形に直せる(=pで割りきれる)ことが分かります。
わかりやすくするため、与式を[p]×[自然数]の形に直すと
\begin{align*}
(1+n)^p - n^p - 1 & = pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}\\
& =p\left[n+\frac{(p-1)}{2!}n^2+\cdots+\frac{(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1} \right ]
\end{align*}
となります。以上より、与式が素数pで割りきれることが明らかになりました。(証明終)
二項定理($ (x+y)^a = \sum_{b=0}^a {_a\textrm{C}_b} x^b y^{a-b}$)を用いて、与式を以下のように変形します。
\begin{align*}
(1+n)^p & - n^p - 1 = \sum_{k=0}^p [ _p\textrm{C}_k n^k 1^{p-k} ] -n^p-1 \\
& = \left[1+pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}+n^p \right ] -n^p-1 \\
& =pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}
\end{align*}
ここで、$ n,n^2,n^3,\ldots ,n^{p-1}$は、すべて自然数です。
また、$ n,n^2,n^3,\ldots ,n^{p-1}$の各項の係数は、組み合わせの個数($ _p\mathrm{C}_k$)ですから、これも自然数です。式から、これらは公約数pをもっていることが分かります。
以上から、与式は[p]×[自然数]の形に直せる(=pで割りきれる)ことが分かります。
わかりやすくするため、与式を[p]×[自然数]の形に直すと
\begin{align*}
(1+n)^p - n^p - 1 & = pn+\frac{p(p-1)}{2!}n^2+\cdots+\frac{p(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1}\\
& =p\left[n+\frac{(p-1)}{2!}n^2+\cdots+\frac{(p-1)\cdots3\cdot2}{(p-1)!}n^{p-1} \right ]
\end{align*}
となります。以上より、与式が素数pで割りきれることが明らかになりました。(証明終)
問題文でn^pとなるべきところがnとなってしまっています。
返信削除>suke1000 さん
返信削除ご指摘ありがとうございます。タイプミス修正しました。
式から、これらは公約数pをもっていることが分かります。
返信削除というところですが、厳密に言うとpCkが約数pを持つことも証明する必要があります。大学入試なら減点を食らう可能性が高いです。