ますらば東大模試(3)解いてみた - werry-chanの日記．料理とエンジニアリング

だいぶ半月前の話になるが，大阪に帰省して奈良とか京都とか行って楽しんでました．
つくばに帰ってきたので仕事の続きをしないといけません．あと実験しないとそろそろ次の国際会議が〆切が見えてきて怖い．

暇つぶしに解いてるますらばの問題(3)です．

前回までに解いてきた(1)
ますらば東大模試(1)解いてみた - werry-chanの日記

問いの(2)です．
ますらば東大模試(2)解いてみた - werry-chanの日記

それでは問題文です．

n を正の整数とする．
(1) p を素数とする．このとき， $n^p-n$ は p で割り切れることを示せ．
(2) $n^2 + 1$ は 4 で割ると 3 余る素因数を持たないことを示せ．

僕，(2)がむずすぎて解けませんでした．
以下に正解を載せますので注意です．

解答です．

まずは(1)です．

帰納法をしたいと思います．

変数がnとpの二つありますね．

これは周知の事かと思われますが，全ての素数pを示す式はありませんので，nを帰納法の変数として動かしてみましょう．

A. n=1で $1^p-1=0$ で割り切れます．

B. kを正の整数として， $k^p-k$ がpで割り切れると仮定する．

C. $(k+1)^p-(k+1)$ について，pで割り切れるか検討する．

$(k+1)^p$ という式の形をみて，一番はじめに思い浮かぶものは，二項定理ですね．二項定理で展開してみましょう．

$(k+1)^p=\sum^p_{i=0} {}_pC_i k^i=\sum^{p-1}_{i=1} {}_pC_i k^i +(k^p+1)$

すなわち，

$(k+1)^p-(k+1)=\sum^{p-1}_{i=1} {}_pC_i k^i +(k^p+1)-(k+1)=\sum^{p-1}_{i=1} {}_pC_i k^i +(k^p-k)-(1+1)$

ここでBより，第二項はpで割り切れる事を仮定している．また第三項は0である．

第1項については

${}_pC_i$ について考えると， ${}_pC_i$ は組み合わせの式なので整数であり，素数pは必ず割り切れない事から ${}_pC_i$ はpの倍数となる．

以上よりCもpで割り切れることがわかった．

ABCより，数学的帰納法より題意は示された．

(2)の解答です．

これ激ムズですね．

正直に言いましょう．解けませんでした．

悔しいですが，公式の模範解答を載せます．

(2) p を 4 で割ると 3 余る素数とする。このとき， $n^2 + 1$ が p を素因数に持つことは， $n^2 + 1$ が p で割り切れることと同値である。

(i) n が p で割り切れるとき

$n^2 + 1 ≡1$ より n + 1 は p の倍数ではない。

(ii) n が p で割り切れないとき明らかに p ≧ 2 である。

x の多項式 $x^p − x$ を x + 1 で割った余りは高々一次式なので ax + b とおけて，その商を Q (x) とすると

$x^p − x = (x^2 + 1)Q (x) + ax + b$ 　　 (2)

$x^2 + 1$ の各項の係数はすべてであるから，

Q (x) の係数はすべて整数である。

この式に x = i(虚数単位) を代入すると

$i^p −i = (i^2 + 1)Q (i) + ai + b$

p は 4 で割ると 3 余る素数であるから，各辺を整理すると

−2i = ai + b

両辺の実部と虚部をそれぞれ比較して，a = −2, b = 0 を得る。

したがって， $n^p − n = (n^2 + 1)Q (n) − 2n$ が成り立つ。

(1) より $n^p − n$ は p の倍数である。

また，n は p の倍数でないので 2nも p の倍数でない。

したがって $(n^2 + 1)Q (n)$ は p の倍数でなく，多項式

Q (n) が整数係数であることに注意すると $n^2 + 1$ も p の倍数ではない。

(i)(ii) より， $n^2 + 1$ は 4 で割ると 3 余る素数 p で割り切れない。

すなわち， $n^2 + 1$ はそのような素数を素因数に持たない。

(証明終)

別解や間違ってるなどありましたらコメントくださいな．

むずかったなぁ(2)．．．解けんかったの悔しいわ．