第２６話 その者、無実の証人なし
「私は素数ではありません。」
その人物は法廷に立たされると、うつむいたまま応えた。これに対し、裁判長が尋ねる。
「証人はいますか？」
「……。おりません…。」
これについて、検察が付け加える。
「被告人はこれまで、我々が推挙した証人すべてに対するフェルマー・テストで、『素数の疑いあり』との判定を受けております。素数である疑いは極めて濃厚です。」
そこで被告人は毅然と顔を上げ、こう言い放った。
「私はカーマイケル数です。」
「…ってことですか？！」
「演出がすぎるわ、たわけ。」
なぜか急にスイッチが入った高木に対し、吉栄光比売がややあきれた顔で言った。
目の前の数字$${n}$$が素数かどうか知るには、その数字と互いに素な数字$${a}$$を持ってきて、$${a^{n-1}}$$を$${n}$$でわったあまりを求める。これをフェルマー・テストといい、フェルマーの小定理によれば、$${n}$$が素数ならそのあまりは必ず$${1}$$になる。言いかえれば、あまりが$${1}$$にならなければ合成数である。
素数かどうかの判定を事件の“犯人”探しにたとえるなら、そこで使う$${a}$$は“証人”と言える。合成数だと言い切ってくれる証人が１人でも見つかれば$${n}$$は“無罪”放免なのだが、気の毒なことに、その証人がまったくいない数というのもあるのだという。それがカーマイケル数である。
「ちなみに、その“証人”とやらのことを、専門用語では底と呼ぶ。」
お茶を飲みながら、吉栄光比売が言った。
「そして、特定の底 ––– $${a}$$としよか ––– でのフェルマー・テストで『素数の可能性あり』てなった数字のことを、$${a}$$を底とする擬素数と呼ぶ。」
「ギ素数？ 容疑者の“疑”っすか？」
大翔が片眉を上げた。
「いや、手偏に“疑う”で“擬”や。擬似的な素数、みたいな意味やな。」
「なるほど。さっきの話だと、$${2}$$を底とする擬素数ですら数字全体の$${0.025\%}$$しかないわけだから、カーマイケル数はもっとすくないってことですね？」
「せやな。$${25000000000}$$までで$${2163}$$コしかあらへん。百分率なら$${0.000009}$$ぱーせんと未満や。」
「すくないなぁ…。」
「SSRや。」
「なんえ、それ？」
「や、なんでもないっす。」
大翔がごまかす。
オンラインゲームなどのガチャで、ごくまれに当たるスーパー・スペシャル・レアなキャラを“SSRキャラ”と呼ぶのだが、ガチャの概念すら知らないであろう女神に説明しても通じまい。
そこで、それまで黙っていた陽菜が聞いた。
「そもそもカーマイケル数ってどういうのんがあるんですか？」
「一番小さいので$${561}$$や。その次が$${1105}$$…。」（参考文献[1]）
そう答えたのは吉栄光比売ではなく、その横に伏せていた狛犬（ヨシザカエもどき）である。それを聞いて、大翔が思わずツッコんだ。
「あー。やっぱ数学できはるんですね…。」
「私を誰や、思てんねん？」
「すみません…。」
もう１頭の狛犬（オッサン）ともども獣の分際で生意気な、と思ってしまったが、よく考えればそもそも彼女（？）は吉栄光比売の分身なのだ。狛犬（オッサン）と違い、おそらく生まれながらにして数学強者なのだろう。
「ええ、でも待ってください。その$${561}$$って、さっき出てきませんでしたっけ？ …ほら。」
陽菜が、さっき狛犬（オッサン）に言われてメモした数字の１つを指差した。たしかに$${561}$$である。
「これってたしか、『$${3}$$でわり切れるから、擬素数ではあるけど素数判定には困らへん』って話と違いましたっけ？」
「ん。それがどないしたんえ？」
狛犬（ヨシザカエもどき）が陽菜に冷たい目を向ける。
「ふえ？！ …えっと…。」
陽菜は言葉につまった。
今まで吉栄光比売本人には優しく接してもらっていただけに、彼女と同じ顔と声の狛犬（ヨシザカエもどき）に冷たくされて面食らったらしい。
「『$${2}$$やら$${3}$$やらでわれたら合成数や』で終いやろ？ それならそもそもフェルマー・テスト自体いらへんよ。」
狛犬（ヨシザカエもどき）が淡々と続けたが、３人はポカンとしている。
「これ、もうちょい丁寧に説明したりぃな。」
「は…、すみません。」
吉栄光比売にたしなめられて、狛犬（ヨシザカエもどき）はすこししょげた顔をした。どうやら分身とは言っても、本人とはいろいろな意味で別個体のようである。
狛犬（ヨシザカエもどき）の説明を、吉栄光比売自らが引き取る。
「ええか。そもそも素数判定をするときは、まず最初に$${2}$$とか$${3}$$みたいな小さな素数でわれるかどうか確認するもんなんや。それで素数かどうかわからん場合に、次の段階としてフェルマー・テストに進むわけや。カーマイケル数が問題になるのは、そのさらに次。」
「その段階で出てくる数字は、さっきの$${561}$$みたいな“雑魚”とは違て、大きすぎて素因数すらわからん。ほれ、おととい大翔が持って来た$${432652837}$$とか、あの領域の数や。あの辺のカーマイケル数やと、フェルマー・テストも手間的には素因数分解してんのと変わらへん。あれかて、素因数分解に苦労したやろ？」
「ああ、たしかに…。」
陽菜が納得した表情を見せた。
「え、ちなみに先生。あの数字はカーマイケル数やったりするんです？」
大翔が身を乗り出す。
「残念。$${2}$$が底の段階でフェルマー・テストにバッチリひっかかる。」
「ちっ。SSRは当たらんかったか…。」
「だから、その“えす・えす・あーる”てなんやねんな…。」
「千坂。『おととい持って来た数字』って何のこと？」
「ん？ おお、そういやまだ言うてへんかったか。昨日もちょっと話したけど、数学徒Xと俺らとで算額のやり取りしててな。それで俺が先方に出した問題が、さっき先生が言うた数字を素因数分解する問題やってん。」
「“数学徒”って…。まあ、わかるけど…。」
「『そこそこ難しくて、かつ俺が答えをわかってる問題』って線で考えたらそこに行きついてな。…先生、まだ数学徒Xから返事返って来てへんのです？」
「いや、まだ返って来てへんなぁ。」
「ふむ。苦戦しとるようやなぁ。してやったりや。」
大翔は無意識に絵馬殿の一番下の段、前回の数学徒Xからの算額がかかっている吊り具を見た。高木も無言でその吊り具を見た。
「じゃあけっきょくのところ、フェルマー・テストがうまく行かへんときってどうするんですか？ このままじゃ、お手上げですよねぇ？」
陽菜が聞くと、吉栄光比売はすこし考えた。
「そこから先はすこし込み入った話になるから、“実験”で説明しよか。」
それを聞いて、陽菜の目がすこしかがやく。
「陽菜。まず試しに、$${n=7}$$、$${a=2}$$やとして、$${a^{n-1}\div n}$$を計算してみ？ 電卓も使てええし。」
「はい！」
彼女はスマホの電卓を駆使して、言われた計算をやった。
$$
\begin{equation*}
\begin{split}
2^{7-1}\div7=2^6\div7=9\ \cdots\ 1
\end{split}
\end{equation*}
$$
「あまりは$${1}$$…ですね。…そら、そうか。フェルマーの小定理あるし。」
陽菜が一人ツッコミをする。それには構わず、吉栄光比売が話を進める。
「その真ん中の辺で、$${2^6}$$が出て来てるやろ？ 今度はその“半分”、$${2^3}$$を$${7}$$でわってみ？」
「$${2^3}$$ですか？」
$$
\begin{equation*}
\begin{split}
2^3\div7=1\ \cdots\ 1
\end{split}
\end{equation*}
$$
「またあまりが$${1}$$になったなぁ。」
大翔が意外そうに言う。高木はアゴに手を当てて考えごとをしている。
「同じことを、今度は$${n=11}$$と$${a=2}$$でやってみ？」
「ええっと…。」
$$
\begin{equation*}
\begin{split}
2^{11-1}\div11=2^{10}\div11&=93\ \cdots\ 1 \\
2^5\div11&=2\ \cdots\ 10
\end{split}
\end{equation*}
$$
「えっと…、これが？」
「ふむ。あまり$${10}$$でもええが、あえてこうしてみたらどうや？」
吉栄光比売は陽菜から紙とシャーペンを受け取り、最後の式をすこし書きかえた。
$$
\begin{equation*}
\begin{split}
2^{11-1}\div11=2^{10}\div11&=93\ \cdots\ 1 \\
2^5\div11&=\textbf{3}\ \cdots\ \textbf{-1}
\end{split}
\end{equation*}
$$
なんと、あまりがマイナスになっている。その代わりに、わり算の答えが陽菜のものよりも$${1}$$大きくなっている。
「え、こんな書き方してええんですか？」
高木がとまどいながら言った。
「ホンマはあかんよ。そやけど、こうした方がこの後の話がわかりやすうなるさかい、あえて規則違反してんにゃ。…ほな、今度は大翔と高木！」（※１）
吉栄光比売が急に２人に話を振った。
「今と同じことを、大翔は$${n=13,\ 17}$$、高木は$${n=19,\ 23}$$の場合にやってみなはれ。手分けや。」
女神がパンパンと手を叩くと、男子２人は顔を見合わせつつ、紙とシャーペンとスマホを取り出した。
$$
\begin{equation*}
\begin{split}
2^{13-1}\div13=2^{12}\div13&=315\ \cdots\ 1 \\
2^6\div13&=5\ \cdots\ \textbf{-1} \\
2^{17-1}\div17=2^{16}\div17&=3855\ \cdots\ 1 \\
2^8\div17&=15\ \cdots\ \textbf{1} \\
2^{19-1}\div19=2^{18}\div19&=13797\ \cdots\ 1 \\
2^9\div19&=27\ \cdots\ \textbf{-1} \\
2^{23-1}\div23=2^{22}\div23&=182361\ \cdots\ 1 \\
2^{11}\div23&=89\ \cdots\ \textbf{1}
\end{split}
\end{equation*}
$$
「おおお…、“半分”にした方の“あまり”、ぜんぶ$${1}$$か$${-1}$$やん。」
「へええ…、なんでやろう？？」
吉栄光比売が湯呑のお茶を飲み切った。
「まぁ証明は難しいから省くけど、$${n}$$が素数なら今の話はぜんぶ正しい。$${a^{(n-1)/2}\div n}$$の“あまり”はかならず$${\pm 1}$$どちらかになる。」（※２）
「$${n}$$が合成数だとどうなんですか？」
「たいがいは成り立たへん。擬素数もこの要領でふるいにかけられることがある。」（※３）
「…やっぱり、完璧ではないんですか。」
「うむ、完璧ではない。ただし、$${a}$$の値を固定したとしたらな。」
To Be Continued…
進んだ注
以下、やや専門的な注釈になります。内容がわからなくてもストーリーには直接関係ないので、興味ある方だけご覧ください。
※１：“あまり”と言った場合、小学校で習うあまり（最小剰余）か、わり算の商とそれに最も近い整数との差（絶対的最小剰余）のいずれかを指す[2]。ここで出てくる“あまり$${-1}$$”は後者の方に該当するが、その場合“$${\cdots}$$”という記号は用いないため、「規則違反」と言っている。
※２：吉栄光比売は「難しい」と言っているが、あくまで数式が苦手な陽菜に合わせた表現である。証明に特別高等な数学が必要になるわけではない。
命題：
$${p}$$を$${2}$$ではない素数、$${a}$$を$${p}$$と互いに素な整数とする。このとき、$${a^{(p-1)/2}}$$を$${p}$$でわったあまりは$${1}$$または$${p-1}$$のいずれかである。
証明：
フェルマーの小定理より、非負整数$${k}$$に対し、
$${a^{p-1}=kp+1.}$$
ここで、$${p}$$は$${3}$$以上の奇数なので、正の整数$${m}$$を用いて
$${p=2m+1}$$
と書けるから、
$$
\begin{equation*}
\begin{split}
a^{2m+1-1}&=kp+1 \\
a^{2m}&=kp+1 \\
a^{2m}-1&=kp \\
\left(a^{m}-1\right)\left(a^{m}+1\right)&=kp
\end{split}
\end{equation*}
$$
右辺が$${p}$$の倍数なので、左辺もまた$${p}$$の倍数。よって、$${\left(a^{m}-1\right)}$$と$${\left(a^{m}+1\right)}$$のいずれか、もしくは両方が$${p}$$の倍数。
仮に両方が$${p}$$の倍数だとすると、適切な正の整数$${k_{\pm}}$$に対し
$$
\begin{equation*}
\begin{split}
a^{m}-1&=k_-p \\
a^{m}+1&=k_+p
\end{split}
\end{equation*}
$$
第$${2}$$式から第$${1}$$式を引くと、
$$
\begin{equation*}
\begin{split}
2=\left(k_+-k_-\right)p
\end{split}
\end{equation*}
$$
$${2}$$は素数であり、また$${p}$$は$${2}$$でない素数なので矛盾する。よって、$${\left(a^{m}-1\right)}$$と$${\left(a^{m}+1\right)}$$のいずれか片方のみ$${p}$$の倍数である。
$${\left(a^{m}-1\right)}$$が$${p}$$の倍数の場合、
$${a^m=k_{-}p+1}$$
なので、$${a^m}$$を$${p}$$でわると$${1}$$あまる。
$${\left(a^{m}+1\right)}$$が$${p}$$の倍数の場合、
$${a^m=k_{+}p-1=\left(k_+-1\right)p+\left(p-1\right)}$$
なので、$${a^m}$$を$${p}$$でわると$${p-1}$$あまる。
Q.E.D.
※３：「同じ要領で」とぼかして表現しているが、$${a^{m}}$$を$${n}$$でわったあまりを見るだけでは不十分である。一般に$${p=1+2^lt}$$（$${t:}$$奇数、$${l:}$$正の整数）と書けることから、（※２）の証明からさらに踏み込んで、
$$
a^{p-1}=\left(a^t-1\right)\cdot\prod_{i=1}^{l-1}\left(a^{2^it}+1\right)
$$
と因数分解する。この右辺は$${p}$$の倍数であり、$${p}$$が素数であればいずれかの因数ただ$${1}$$つが$${p}$$の倍数になる。$${p}$$が合成数の場合そうならない可能性がある。多くの場合はそうならないが、底$${a}$$を$${1}$$つに固定する限り、素数と同様の性質を示す合成数が存在する。それらを、$${a}$$を底とする強擬素数と呼ぶ。
参考文献
[1] "ON-LINE ENCYCLOPEDIA OF INTEGER SEQUENCES" by N. J. A. Sloane
[2] 「初等整数論講義 第２版」 高木貞治 著 共立出版株式会社
[3] 「素因数分解と素数判定」 デヴィッド・M・ブレッソード 著、玉井浩 訳 SiB access