流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

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

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

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

 

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

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

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

まずは観察と実験から

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

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)

が成り立つ。

 ここで、51から順にべき乗していったときに、はじめて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)式より、2qp-1は共に\lambdaの倍数である。したがって、ある正の整数k,lにより、

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

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

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

ここで、q素数なので、kまたはp-1を割り切る。ところが、仮定よりp-1 \lt p \le qなので、qp-1を割り切らず、kqの倍数であることが言える。よって、ある正の整数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)

これを満たす素数pp=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 群論入門 (代数学シリーズ)

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

 

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

群論への30講 (数学30講シリーズ)

群論への30講 (数学30講シリーズ)

 

 

*1:q \ge p=3は奇数より。

*2:p-1q-1が、必ずしもそのような最小の正の整数になっているとは限らないことに注意!!

*3: (7)、(8)式を満たす整数が少なくとも1つ存在することは(3)、(4)式よりわかっているので、このような数が存在することがわかる。

*4:このことの証明は、着目する数が倍数でないと仮定して、その数\lambda,\muで割ったときの余りに着目するといい。背理法により、矛盾が導ける。

*5:群論では、ラグランジュの定理(ラグランジュの定理 (群論) - Wikipedia)で説明される。