【素数p,q】5^p+1がqで割り切れ、5^q+1はpで割り切れる

整数問題bot②で見かけた良問

　昨日(今日)の深夜に整数問題bot②で、ある問題がふと目についた。次のツイートである。

素数の組(p,q)であって, 5^p+1がqで割り切れ, かつ5^q+1がpで割り切れるようなものを全て求めよ.
(出典はヒ・ミ・ツ(^_-)❤)
— 整数問題bot② (@handmade_math) 2018年7月17日

「出典はヒ・ミ・ツ♡」とか書いてあるのがお茶目で、すごく気になったのだ。
この問題、最初はどこから手を付けるかやや悩んだ。(深夜で頭の回転が鈍っていたのかもしれないが……)

　この問題を解き終わったとき、少し前に勉強した群論の知識がうまく使えて、本で勉強した知識を再確認でき、理解が一歩研ぎ澄まされた感じがした。つまり、群論を少し勉強した人にとって、この問題は良問だと思うので紹介してみたい。

　ここでの解説は、群論の知識が無い高校生でも読めるように書いてみるので、整数問題が好きな高校生でも楽しめると思う。

まずは観察と実験から

　まとまった解答は後で書くことにして、まずは問題を見て最初にやってみたことから紹介していこうと思う。このブログでは単に解答を紹介するだけじゃなくて、問題を解くときのライブ感も伝えてみたいからだ。この問題、初見ではどこから手をつけたらいいかすぐにはわからないだろう。そこで、具体的な小さな数で試してみる。解ける兆しが見えていないときでも、自分の手で一歩一歩問題に取り組むのが大切で、もし解けなくても「今の自分がどこまで行けるのか」を知ることが次の挑戦・成長にきっと繋がるからだ。

$p \le q$ として一般性を失わないので、 $p=2,3,5$ の場合をまずは試してみよう。

問題の式は、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

と書ける。

まず、 $p=2$ のとき、 $5 \equiv 1 (\bmod 2)$ より、

$5^q+1 \equiv 1+1 \equiv 0 (\bmod 2)$
$5^2+1 \equiv 26 = 2 \times 13 \equiv 0 (\bmod q)$

よって、 $(p,q)=(2,2),(2,13)$ が解の一つであることがわかる。

次に、 $p=3$ のとき、 $5 \equiv -1 (\bmod 3)$ より、

$5^q+1 \equiv (-1)^q+1 = 0 (\bmod p)$ *1
$5^3+1 \equiv 126 = 2 \times 3^2 \times 7 \equiv 0 (\bmod q)$

よって、 $(p,q)=(3,3),(3,7)$ も解である。

$p=5$ のときは、 $5 \equiv 0 (\bmod 5)$ より、

$5^q+1 \equiv 1 (\bmod 5)$

となるので題意を満たさない。

　ここまでやってみて、見つかった解に規則性らしきものがなさそうに感じられるので、ひょっとしたら、 $p \ge 5$ の解は存在しないんじゃないかという気がしてくる。
実際、 $p=2,3$ 以外に解が無いことは後になってわかるが、前に進むために(1)、(2)式を少し変形してみる。

$5^p \equiv -1 (\bmod q)$ ……(1')
$5^q \equiv -1 (\bmod p)$ ……(2')

この式をしばらく見つめてみる。すると、右辺が $-1$ だから取扱いにくいのかなと思えてくる。そこで、(1')、(2')式の両辺を二乗して右辺を $1$ にしてみることにした。

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

　ここで、上の式がフェルマーの小定理(フェルマーの小定理 - Wikipedia)に似ていることに気づく。フェルマーの小定理を書き出してみると、 $p,q \not\equiv 5$ のとき、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。

　ここで、 $5$ を $1$ から順にべき乗していったときに、はじめて $1$ になるのはいつだろうかと考えてみることにした。*2このようなアイデアに自然に行き着いたのは、群論を勉強していたおかげだと思う。ともかく、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数 $\lambda,\mu$ を考える。*3　このとき、(3)(4)(5)(6)式の指数は、それぞれ対応する $\lambda,\mu$ の倍数であることがわかる。*4 *5

もし、(7),(8)を満たす $\lambda,\mu$ が具体的に求まれば、 $p-1$ 乗や $q-1$ 乗といった考えにくい式は扱わなくてすむだろう。そんなわけで、この問題を解く方針が定まった。それでは、解答に移ろう。

解答

$p \le q$ として一般性を失わない。題意より、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

であるが、これを変形して、

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

を得る。 $p,q \equiv 5$ の場合、(3)(4)式は明らかに成立しないので、以下 $p,q \not\equiv 5$ として考える。すると、フェルマーの小定理より、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。次に、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数を $\lambda,\mu$ とおくと、(4)(6)(7)式より、 $2q$ と $p-1$ は共に $\lambda$ の倍数である。したがって、ある正の整数 $k,l$ により、

$2q=k \lambda$ ……(9)
$p-1=l \lambda$ ……(10)

この２つの式より、(9)式の両辺を $l$ 倍して、

$2 q l = k l \lambda = k(p-1)$ ……(11)

ここで、 $q$ は素数なので、 $k$ または $p-1$ を割り切る。ところが、仮定より $p-1 \lt p \le q$ なので、 $q$ は $p-1$ を割り切らず、 $k$ が $q$ の倍数であることが言える。よって、ある正の整数 $m$ が存在して、

$k=mq$ ……(12)

が得られる。これを(9)式に代入すると、

$2q=mq \lambda$
$2=m \lambda$ ……(13)

となり、 $m,\lambda$ が正の整数であることから、

$\lambda=1,2$ ……(14)

であることがわかった。

① $\lambda=1$ の場合、

(7)式より、

$5^1\equiv 1 (\bmod p)$ ……(15)

これを満たす素数 $p$ は $p=2$ のみである。

② $\lambda=2$ の場合、

(7)式より、

$5^2=25 \equiv 1 (\bmod p)$ ……(16)
$5^1 \not\equiv 1 (\bmod p)$ ……(17)

ここで、(16)式を満たす素数 $p$ は、 $p=2,3,\cdots$ と調べていくことで、 $p=2,3$ のみであることがわかる。 $p=2$ は(15)式を満たすので、(17)式を満たさない。よって、 $\lambda=2$ の場合、 $p=3$ となる。

　以上より、題意を満たす素数 $p(\le q)$ は、 $p=2,3$ しか存在しないことが分かった。よって、求める解は、 $p \le q$ の条件を取り除くと、

$(p,q)=(2,2),(2,13),(13,2),(3,3),(3,7),(7,3)$

だけであることがわかる。

最後に本の紹介

今回の問題が解けたのは、群論を雪江先生の本で勉強していたことが大きかったと思う。そこで、群論に興味がある人のために、以下の本をおススメしておく。

代数学1　群論入門 (代数学シリーズ)

作者: 雪江明彦
出版社/メーカー: 日本評論社
発売日: 2010/11/17
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 21回
この商品を含むブログを見る

自分で読んだときは、数か所証明が分からないところもあったが、主要な部分は独学でも一通り理解できたので親切な良書だといえるだろう。ページ数も150ページ程度なので、頑張れば１～２週間くらいで読めるだろう。定理に対して例も豊富だが、ところどころ証明の要点があっさり書かれすぎている印象をいくらか受けた。数学科の優等生はこれで問題ないのだろうが、ここでつまづく人や独学の人は志賀先生の「群論への30講」を先に読んでみるのもいいと思う。ちなみに、こちらは少し頑張れば5~7日くらいで読めると思う。