2016年 京都大学整数問題を今更解いてみた

問題

$2016\text{年京都大学}$
$p^q+q^p$が素数となるような$素数p,q$を全て求めよ．

解答

明らかにわかること

$p,q$は素数であることから明らかに$p,q\ge 2$即ち$p^q+q^p\ge 2^2+2^2=8$であるので，$p^q+q^p$は奇素数でなければならい．即ち，$p, q$のどちらかが偶素数でもう片方が奇素数でなければならない．そこで，ひとまず$p=2,q\in\mathfrak{Odd}$¹と仮定して以後議論をしていく．

実験してみてあたりを付ける

ノーヒントの状態から，これが答えだと言い切るのは，私もRamanujanじゃないので無理．なので，とりあえず奇素数$q$の当たりを付けてから，それが正しいことを証明していくことにする．
こんなことは受験中できるはずもないが，計算機で実験してみる

$2^q+q^2$が素数となる$q$の当たりをつけるSageMathスクリプト

for q in range(3, 50, 2):
    print(f"{q}: {factor(2^q+q^2)}")

実行結果

3: 17
5: 3 * 19
7: 3 * 59
9: 593
11: 3^2 * 241
13: 3^2 * 929
15: 32993
17: 3 * 43787
19: 3 * 179 * 977
21: 2097593
23: 3 * 67 * 41737
25: 3 * 11185019
27: 73 * 521 * 3529
29: 3^3 * 11 * 41 * 44089
31: 3^3 * 79536467
33: 8589935681
35: 3 * 19 * 602802449
37: 3 * 193 * 9203 * 25793
39: 17 * 43 * 752059939
41: 3 * 11 * 17 * 3919827553
43: 3 * 2932031008019
45: 11 * 17 * 5689 * 33072899
47: 3^2 * 41 * 1217 * 313395569
49: 3^2 * 163 * 403537 * 950947

値を見てみると，どうやら$q\perp 3$のときは$3\mid 2^q+q^2$らしい．ということで，これを証明してみよう．

$\mathrm{Claim\ 1}$
${}^\forall q\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp q \ \longrightarrow\ 3\mid 2^q+q^2\right)$

証明

以下，$\mathbb{F}_3$上の演算とする．

\begin{align*}
    2^q+q^2&=2^q+1\quad(\because q=1,2)\\
    &=2+1\quad (\because q\in\mathfrak{Odd})\\
    &=0
\end{align*}

以上の計算から$3\mid 2^q+q^2$．$\quad \square$

非常にわかりにくいが，$2^q$の肩に乗ってる$q$は整数，つまり$\mathbb{Z}$の元と見なし，$q^2$の$q$は有限体$\mathbb{F}_3$の元と見なしていることに注意されたい．

よって，$q$は$3$の倍数でなければならない．$3$の倍数であって素数であるものは$3$のみ，そして実際に代入すると$p^q+q^p=2^3+3^2=17\in\mathfrak{Prime}$²で，確かに素数になっている．

ちゃんとした解答

$p,q$が素数であることから明らかに$p^q+q^p\ge 8$であるので，$p^q+q^p$は奇素数でなければならない．偶数と偶数，奇数と奇数の和はそれぞれ偶数となり不適であるから，片方が偶数，もう片方が奇数でなければならず，偶素数は$2$に限られる．$p^q+q^p$は明らかに$p,q$に関して対称なので$p=2$と仮定しても一般性を失わない．
ここで，以下の主張を証明する．

$\mathrm{Claim}$
$q\in\mathbb{Z}$が$3\perp q$なる奇数であるとき，$3\mid 2^q+q^2$

証明

以下，法は$\bmod 3$とする．$q$は奇数であり，かつ$3$と互いに素であるから以下が成立する．

\begin{align*}
    2^q+q^2\equiv 2^q+(\pm1)^2\equiv 2^q+1=(-1)^q+1\equiv -1+1\equiv 0.
\end{align*}

従って，$3\mid 2^q+q^2$である．$\quad \square$
上の主張から，$q$が3と互いに素であるときは，$2^q+q^2(>3)$は合成数となってしまうことがすぐに分かるため，$q$は3の倍数でなければならない．$3$の倍数であるような素数は$3$のみしか存在しないので$q=3$．また，このとき$p^q+q^p=2^3+3^2=17$であり，確かに素数である．
以上から，求める素数の組は$(p, q)=(2, 3), (3, 2)$．

たま～に気が向いたらこういう問題を解いてみるのも良いですねぇ．

10月21日追記：変数を多くして考察してみた

3変数の場合

自然な変数の増やし方はいくつかあるが，$p^{qr}+q^{pr}+r^{pq}$を考える．つまり，一般に$n$変数の場合は$ \sum_{i=1}^n p_i^{\prod_{1\le j\le n, j\ne i}p_j}$を考えることになり，$n=2$のときは$p_1^{p_2}+p_2^{p_1}$になっており，自然な一般化になっていることがわかる．また，$p,q,r$が全て奇素数であるときは少々面倒なので，$p,q,r$のうち，少なくとも1つが偶素数，即ち$2$のときを考える．

1つだけ$2$の場合

この場合は$p^{qr}+q^{pr}+r^{pq}\in\mathfrak{Even}$であるから明らかに合成数である．

2つ$2$の場合

この場合も，実は次のことが簡単に確かめられる．

$\mathrm{Claim\ 2}$
${}^\forall r\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp r \ \longrightarrow\ 3\mid 2^{2r}+2^{2r}+r^4\right)$

証明

以下，$\mathbb{F}_3$上の演算とする．

\begin{align*}
2^{2r}+2^{2r}+r^4=1+1+r^4&=1+1+1\quad (r=1, 2)\\
&=0.\quad \square
\end{align*}

このClaimから，素数になるのであれば，$(p, q, r)=(2, 2, 3)$であり，これを代入してみると$209(=11\times 19)$となり素数とはならない．

因みに$p, q, r$が全て奇素数であるときを考えた場合は，SageMathに計算させてみると

p = 3, q = 3, r = 5, hoge = 11 * 149 * 18701
p = 3, q = 3, r = 7, hoge = 20961060013
p = 3, q = 3, r = 11, hoge = 109 * 102001132945493
p = 3, q = 3, r = 13, hoge = 389 * 20835759168746663
p = 3, q = 3, r = 17, hoge = 101 * 4129 * 38693 * 74827 * 3567442589
p = 3, q = 3, r = 19, hoge = 5 * 31 * 35803 * 729166393 * 776003632169
p = 3, q = 3, r = 23, hoge = 122489 * 749339302333 * 18181134121513417
p = 3, q = 3, r = 29, hoge = 53 * 530878067 * 1334978377 * 17212116315350476676309
p = 3, q = 3, r = 31, hoge = 83 * 1901 * 2411 * 10663 * 140313319 * 385498283 * 2148070397118859
p = 3, q = 3, r = 37, hoge = 2203 * 542483 * 739187 * 343293481 * 2182359929 * 275894081245658919833
p = 3, q = 3, r = 41, hoge = 5 * 419 * 2383194439905856823 * 19435728418432679673996997817058935479
p = 3, q = 3, r = 43, hoge = 33937 * 4502639473 * 14376217013 * 1067180039540999 * 30175113904892553377707
p = 3, q = 3, r = 47, hoge = 53 * 149 * 5874721 * 75129451620623285621 * 10786171173949234205297534015831566249
p = 3, q = 5, r = 13, hoge = 3^2 * 5^2 * 17^2 * 30703 * 1539257 * 3352632326525939
p = 3, q = 5, r = 17, hoge = 67 * 26813 * 33829 * 50857 * 1136831 * 10222473751764276637p = 3, q = 5, r = 19, hoge = 3^2 * 959183 * 245683865671701626015750122806121614973
p = 3, q = 5, r = 23, hoge = 11 * 23^2 * 773 * 163859 * 19291343 * 398821559 * 1304082753323154929341734659
p = 3, q = 5, r = 29, hoge = 2366123 * 643494173646761109937983439220179795185124164748209609961780079
p = 3, q = 5, r = 31, hoge = 3^2 * 1329197 * 5246359577 * 1432532775245237142306363986862861504322380743212216054123       
p = 3, q = 5, r = 37, hoge = 3^2 * 29 * 70923737837282449529980272056401444804100429902259207408335088564774016863686418825401
p = 3, q = 5, r = 41, hoge = 28867 * 2235916420027422610502984177619148101378096395503528450007395389348396973259216481220196000707
p = 3, q = 5, r = 43, hoge = 3^3 * 13 * 3592366834539773 * 316225652926269061 * 557786446197635796535608058681 * 17136294413883638574255608024912672773
p = 3, q = 5, r = 47, hoge = 5^2 * 13 * 2130686492756021 * 17596660998232895911270373 * 1090590419022615847557595460542031600607554360982954819911400613767643
p = 3, q = 7, r = 5, hoge = 3^5 * 5^2 * 37 * 503 * 446774407
p = 3, q = 7, r = 7, hoge = 239300446322345696158097
p = 3, q = 7, r = 11, hoge = 3^2 * 11^2 * 111049643 * 45268027135072503807483103
p = 3, q = 7, r = 13, hoge = 103 * 211 * 585588859 * 3279392181661 * 627376629959533709
p = 3, q = 7, r = 17, hoge = 3^2 * 13 * 5119687464143786262618448504743280174986799476845663431
p = 3, q = 7, r = 19, hoge = 37 * 412411 * 2196869496801609016817 * 85465463924413088918212180820735371
p = 3, q = 7, r = 23, hoge = 3^3 * 23^2 * 700459 * 124902638183 * 52450332090372848217245325022389203432447366078557058383
p = 3, q = 7, r = 29, hoge = 3^2 * 397729 * 12348799 * 6368256047261995643 * 25476496377527141766273899502782093525888349483366679841598928987
p = 3, q = 7, r = 31, hoge = 191 * 659 * 272516932831043819208841144972708829758912810099195278102190045557117496402159670650743904373682029
p = 3, q = 7, r = 37, hoge = 67 * 149916419 * 373663751633293568099930684961999800760623814979086552393748664192438333359391770467435806251005648457161234920239
p = 3, q = 7, r = 41, hoge = 3^3 * 1229 * 2099 * 24163091 * 51017541852771800241258223879500483240083831766293815751876597586981762399479378226243279687779548163025139545768473517293
...

という結果が得られた．なんとなく分かるかとは思うが，ここでhogeは$p^{qr}+q^{pr}+r^{pq}$のことを表している．尚，コードは以下．

for p in xsrange(3, 50):
    for q in xsrange(3, 50):
        for r in xsrange(5, 50):
            if is_prime(p) and is_prime(q) and is_prime(r):
                print(f"p = {p}, q = {q}, r = {r}, hoge = {factor(p ^ (q * r) + q ^ (p * r) + r ^ (p * q))}")

$\left\lbrace \left. (p, q, r)\in\mathfrak{Prime}^3\ \right|\ p^{qr}+q^{pr}+r^{pq}\in\mathfrak{Prime}\right\rbrace$が有限集合なのかは分からないので，もしわかる方がいたら教えてください．

一般の$n$変数の場合

2変数の場合と3変数の場合の双方においてClaim 1, 2のようなものが成立していた．この2つだけを見てみるともしかしたら

{}^\forall n\in\mathbb{Z}_{\ge 2}\left({}^\forall p\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp p \ \longrightarrow\  3\mid (n-1)\times 2^{(n-1)p}+p^{2(n-1)}\right)\right)

が成立するのではないか，という淡い期待を一瞬だけ持ってしまう．しかし，そんなことはない．というか明らかに成立しない．例えば$n=4$としてみれば

3\times 2^{3p}+p^6\equiv p^6\equiv 1\quad (\bmod\ 3)

であり，$3$で割り切れない．では逆に，どのような条件のとき成立するのだろうか．

{}^\forall p\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp p \ \longrightarrow\  3\mid (n-1)\times 2^{(n-1)p}+p^{2(n-1)}\right)

の必要十分条件を考えてみよう．

\begin{align*}
    (n-1)\times 2^{(n-1)p}+p^{2(n-1)}&\equiv (n-1)\times 2^{(n-1)p}+1\\
    &\equiv (n-1)\times 2^{n-1}+1\quad (\because p\in\mathfrak{Odd})\\
    &\equiv (n-1)\times (-1)^{n-1}+1\quad (\bmod\ 3)
\end{align*}

と簡単に分かる．つまり，$3\mid (n-1)\times (-1)^{n-1}+1$であれば良い．試しにまたSageMathで実験してみる．

$3\mid (n-1)\times (-1)^{n-1}+1$であるような$n$の当たりをつけるSageMathスクリプト

for n in xsrange(2, 51):
    print(f"{n}: {((n - 1) * (-1) ^ (n - 1) + 1) % 3}")

実行結果

2: 0
3: 0
4: 1
5: 2
6: 2
7: 1
8: 0
9: 0
10: 1
11: 2
12: 2
13: 1
14: 0
15: 0
...
48: 2
49: 1
50: 0

どうやら，$n\equiv 2, 3\quad (\bmod\ 6)$のときに限り$3$の倍数になるらしいので，これを証明してみよう．

証明

以下，$m$は勝手な整数とする，

• $n\equiv 0\quad (\bmod\ 6)$のとき
  $(6m-1)\times (-1)^{6m-1}+1\equiv 1+1\not\equiv 0\quad (\bmod\ 3)$
• $n\equiv 1\quad (\bmod\ 6)$のとき
  $6m\times (-1)^{6m}+1\equiv 0+1\not\equiv 0\quad (\bmod\ 3)$
• $n\equiv 2\quad (\bmod\ 6)$のとき
  $(6m+1)\times (-1)^{6m+1}+1\equiv -1+1\equiv 0\quad (\bmod\ 3)$
• $n\equiv 3\quad (\bmod\ 6)$のとき
  $(6m+2)\times (-1)^{6m+2}+1\equiv 2+1\equiv 0\quad (\bmod\ 3)$
• $n\equiv 4\quad (\bmod\ 6)$のとき
  $(6m+3)\times (-1)^{6m+3}+1\equiv 0+1\not\equiv 0\quad (\bmod\ 3)$
• $n\equiv 0\quad (\bmod\ 6)$のとき
  $(6m+4)\times (-1)^{6m+4}+1\equiv 1+1\not\equiv 0\quad (\bmod\ 3)$
  以上より，$3\mid (n-1)\times (-1)^{n-1}+1$となるのは$n\equiv 2, 3\quad (\bmod\ 6)$のときに限られる．$\quad \square$

以上から，

{}^\forall p\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp p \ \longrightarrow\  3\mid (n-1)\times 2^{(n-1)p}+p^{2(n-1)}\right)

は$n\equiv 2, 3\quad (\bmod\ 6)$と同値であることが分かった．より，格好つけて書くならば

\left\{n\in\mathbb{Z}_{\ge 2}\  \left| \ {}^\forall p\in\mathfrak{Odd}\cap \mathbb{Z}_{>0}\left(3\perp p \ \longrightarrow\  3\mid (n-1)\times 2^{(n-1)p}+p^{2(n-1)}\right)\right.\right\}=(6\mathbb{Z}+2)\cup(6\mathbb{Z}+3)

である．

1. $\mathfrak{Odd}$はここでは奇数全体の集合を表している．これは私の癖であり，みんながみんな使うわけではなく$q:\text{奇数}$や$q:\text{odd}$，$q\in \text{odd}$や$q\in\mathbb{O}$など，幾つかの書き方を見たことがある． ↩

2. $\mathfrak{Prime}$も$\mathfrak{Odd}$同様に素数全体の集合を表している． ↩