712! + 1 は素数か？
概要
なんかネットで見かけた問題
初出はエストニアの国際数学大会 Baltic Way の 2014 の 16 問目だそう
https://gyazo.com/ee1624bfebec992cbb6a47365e84e081
Estonian Math Competitions
解答を見ると素数じゃないのだけど、その説明が突然「719は素数なので」から始まり納得できない
https://gyazo.com/10c256f13df526d908aeb1e6e8c09229
もうちょっと私なりに筋道を立てて行きたい
気持1: 多分素数じゃないよね
仮にこれが素数だとして、それを限られた紙の上でコンピュータもなしに示せるわけがない だから、この数の素因数を探し出して割り切って見せるのが一番早い
ただし、$ 712 以下の素因数は持たないことが確実
次点で素数にまつわる何らかの法則で合成数であることを示すかだ
$ p が素数 \Leftrightarrow (p-1)! \equiv -1 \pmod p
$ 713=23\cdot31 なので素数じゃなかった
このままは使えないけど階乗が出てくるので何かで使う可能性は高い
気持3: そう言えば 6! = 720 じゃん
先述のウィルソンの定理より 7 が素数だから $ 6! \equiv -1 \pmod 7
そういうわけで $ 6!+1=721 は 7 の倍数だけど $ 6!-1=719 は素数の可能性高いのでは？
ここまでの話で 7 より大きい素数だけ試せばいい
$ 29^2 > 719 は何となく分かるので $ 11, 13, 17, 19, 23 で割るのを試せばいい
ただし 23 はさっき 713 を割り切ったので候補から外れて $ 11, 13, 17, 19
除数が全て奇数かつ一の位が 9 なので、通常の割り算の筆算とは逆に下の位から計算すると早い
一の位が 5 以外の奇数は掛ける前と後の値が 1 対 1 対応するので確実
余りはどうでもよくて割れるかどうかだけ知りたいので下一桁の辻褄が合うように下の桁から計算していく
というわけで 719 は素数でした
気持3': 713 より上の素数を探そう
720 という天啓が降ってこなくてもとりあえず 713 より上の素数を順繰りに探していく
判別のむずい素数の 713 付近の倍数を探そう
$ 713=\bm{23}\cdot31
$ 714 = \bm{7}\cdot2\cdot3\cdot\bm{17}
7 の倍数見つけて割ってたら 17 もでてきた
$ 715=\bm{11}\cdot5\cdot\bm{13}
$ 722=\bm{19}^2\cdot2
717 は 3 の倍数だから、719 が 713 以上で最小の素数
最初に思いついたのは 720 からの連想だったけど、713 以降でエラトステネスの篩する方が簡単だし確実そうに思えた
割り算を繰り返すのはしんどいが、逆に掛け算で合成数を絞り込むのは大変じゃないし、複数の数から素数を見つけ出すには確実
719 でウィルソンの定理を使う
719 にたどり着けばその先は模範解答と同じ
$ 718! \equiv -1\pmod{719} ←ウィルソンの定理
712! を捻出したいな……
$ 718!=718\cdot717\cdot716\cdots713\cdot712!
$ \equiv (-1)\cdot(-2)\cdot(-3)\cdots(-6)\cdot712!\pmod{719}
$ =(-1)^6\cdot6!\cdot712!=1\cdot720\cdot712!
$ \equiv712!\pmod{719}
$ \therefore 712!+1\equiv718!+1\equiv0\pmod{719}
与式は 719 で割り切れました やったね！
もし、問題が 713! とかだったらこの方法じゃ解け無さそう