魔法少女まどか☆マギカ10話の問題を解いてみた
魔法少女まどか☆マギカ10話が無事ニコニコ動画で視聴可能に。ニコニコでまどか☆マギカを見るのは3話以来。当時はネタバレコメントやタグが多くて困ったのだが、今やそういう事もなくなり視聴者のマナーが良くなっている印象(さすがに今回は見てる人多いだろうから配慮したのかも)。
で。折角なので10話ででてきた問題を解いてみたよ。
問題は
pは素数、nは任意の自然数とします。 (1+n)^p - n^p - 1がpで割り切れることを証明してください。
というもの。中学生までで習う知識で解けるけれど、ちょっと中学生には程度が高いような気がしないでもない。解いた結果を以下に解説してみる。
問題を解くときはできるだけ簡単な場合から考える。今回だと素数pのことは一旦忘れてpのかわりに任意の自然数aを使ってみる。でaにいろいろな値を入れて式を展開してみると以下のようになる。
a=1の場合 (1+n)^1 = 1 + n a=2の場合 (1+n)^2 = 1 + 2n + n^2 a=3の場合 (1+n)^3 = 1 + 3n + 3n^2 + n^3 a=4の場合 (1+n)^4 = 1 + 4n + 6n^2 + 4n^3 + n^4
ここで注目したいのは展開後の式の各項の係数。それぞれの項の係数がいくつになるかというのは二項定理というもので計算できる。詳しくはこちらを参照されたい。
で。二項定理によると前からk+1番目の項の係数は以下で計算できる。
a! / {(a-k)! * k!}例えば(1+n)^3の場合は
(1+n)^3 = 1 + 3n + 3n^2 + n^3
1番目の項(a=3,k=0) 3! / {3! * 0!} = 1
2番目の項(a=3,k=1) 3! / {2! * 1!} = 3
3番目の項(a=3,k=2) 3! / {1! * 2!} = 3
4番目の項(a=3,k=3) 3! / {0! * 3!} = 1となり正しく係数が計算できていることがわかる。
さて、係数が二項定理で計算できることが分かったのでa(自然数)ではなくp(素数)の場合に戻す。そもそも問題は
(1+n)^p - n^p - 1 がpで割り切れることを示す。
というものだった。ここで式をよくみるとn^pは(1+n)^pを展開したときの最後の項。1は(1+n)^pを展開したときの最初の項になっている。つまり(1+n)^pを展開した式で2番目(k=1)からp-1番目(k=p-2)までの項がpで割り切れれば良い(=pを素因数としてもっていればいい)。
二項定理によりk+1番目の項は以下の式で計算できる(今回はaではなくpとしている点に注意)。
p! / {(p-k)! * k!}これを式変形して以下のようにする。
p! / {(p-k)! * k!}
= {p * (p-1)!} / {(p-k)! * k!}
= p * [(p-1)! / {(p-k)! * k!}]すると(1+n)^p - n^p - 1の各項(上の式)はpを素因数として含んでいるように見える。見える、と歯切れの悪い言い方をしたのは他の項(p-1)!、(p-k)!、k!にpが含まれているとpの数が増えたり減ったりしてしまうのでpを素因数として持つと言い切れなくなる。よって(p-1)!、(p-k)!およびk!の素因数にpが含まれないことがわかればいい。
(p-1)!はp-1以下の自然数の積。(p-k)!はp-k以下の自然数の積。k!はk以下の自然数の積。なのでkが1以上であれば(p-1)!も(p-k)!もk!もpを素因数として含まないことがわかる(k=0だと(p-k)!=p!なので)。
よって(1+n)^p - n^p - 1の各項はpを素因数として含んでいる。よってpで割り切ることができる。各項がpで割り切れるので - n^p - 1はpで割り切れる。
以上。おしまい。
