京大2016とマケドニア数オリ2013

素数

399

この記事では素数に関する 2 つの問題を紹介し、それらを一般化した問題を考察します。

京大 2016

まず次の問題を紹介します。

京大 2016

素数$p,q$を用いて$p^q+q^p$と表される素数をすべて求めよ。

この問題の解答は次のようになります。

偶数の素数は 2 のみなので、$p,q$の偶奇が一致するとき、$p^q+q^p$は 2 より大きい偶数となり素数でない。よって$p,q$の一方は偶数であり 2 に等しい。$q=2$としてよい。このとき$p$は奇素数である。$2^p\equiv (3-1)^p\equiv (-1)^p\equiv -1\pmod{3}$となる。$p$を 3 で割った余りを考えると

$p\equiv 1\pmod{3}$のとき、$p^2\equiv 1\pmod{3}$より、$p^2+2^p\equiv 0\pmod{3}$。
$p\equiv 2\pmod{3}$のとき、$p^2\equiv 1\pmod{3}$より、$p^2+2^p\equiv 0\pmod{3}$。

よって$p$が 3 の倍数でないときは$p^2+2^p$は 3 の倍数で、素数でない。最後に$p$が 3 の倍数のときは$p=3$であり、$3^2+2^3=17$は素数である。
以上より、条件を満たす素数は 17 のみである。

偶奇 (つまり 2 で割った余り) と 3 で割った余りに着目する問題でした。

Macedonia National Olympiad 2013

続いて次の問題を紹介します。表記は少し変えてあります。

Macedonia National Olympiad 2013

素数$p,q$を用いて$p^{2q}+q^{2p}$と表される素数をすべて求めよ。

この問題も上の問題と同様の手法で解けるので、ぜひ挑戦してみてください。答えだけ書くと、このような素数は存在しません。

一般化

紹介した 2 つの問題はよく似ています。一般化をしたくなりますね。そこで、次のような問題を考えてみましょう。

正の整数$n$と素数$p,q$を用いて$p^{nq}+q^{np}$と表される素数をすべて求めよ。

まず$p,q$の一方が偶数であることがわかるので、$q=2$としましょう。$p^{2n}+2^{np}$と表される素数をすべて求める問題となります。

$n$が奇数の場合を考えてみましょう。

$n$が奇数ならば、素数となるのは$(n,p)=(1,3)$のときのみ。

$n$が奇数のとき$x^n+y^n$は$x+y$で割り切れる。よって$p^{2n}+2^{np}$は$p^2+2^p$で割り切れる。$p^2+2^p$が素数になるのは問題 1 より$p=3$のときのみ。

次に、$n$が奇数で割り切れる場合を考えてみましょう。

$n$が 3 以上の奇数$k$で割り切れるとき、素数とならない。

$n=km$とおく。$x^n+y^n=(x^m)^k+(y^m)^k$は$x^m+y^m$で割り切れる。よって$p^{2n}+2^{np}$は$p^{2m}+2^{mp}$で割り切れ、$k\ge 3$なので素数でない。

これで、残りは$n$が 2 べきの場合になりました。$n=2$の場合は問題 2 で考えたので、$n=4$を考えてみましょう。

$p$	$p^{2n}+2^{np}$	素因数分解	素数か
3	$10657$	$10657$	〇
5	$1439201$	$193 \times 7457$
7	$274200257$	$274200257$	〇
11	$17592400403297$	$1201 \times 14648 126897$
13	$4503600443101217$	$17 \times 593 \times 113233 \times 3945329$
17	$295147905186328583297$	$353 \times 577 \times 6257 \times 395953 \times 584897$
19	$75557863725931306982177$	$17 \times 4444580219172429822481$

素数が 2 つありました。他の$n$でも実験してみたところ、次の場合に素数になることが分かりました。

$(n,p)=(4,3)$のとき$10657$
$(n,p)=(4,7)$のとき$274200257$
$(n,p)=(8,5)$のとき$1252099518401$
$(n,p)=(8,11)$のとき$309485009867294798588353217$
$(n,p)=(32,3)$のとき$3512911982806776822251393039617$

他に素数があるかはわかっていません。

素因数に関する考察と予想

$p^{2n}+2^{np}$の素因数分解を調べていたところ、$n=32$のときに 257 が素因数に多く現れることに気がつきました。

$p$	$p^{2n}+2^{np}$の最小の素因数 ($n=32$)
5	641
7	1284737
11	141697
13	257
17	1153
19	13441
23	769
29	257
31	257
37	4993
41	10753
43	305281
47	2689
53	24048001
59	257
61	257
67	60289
71	769
73	3329
79	257
83	769
89	257

257 といえば $2^{2^3}+1$と表されるのでフェルマー素数です。この素数が素因数に多く現れるのには何か理由があるのではないかと思い調べました。すると、上の表にある素因数はすべて 128 で割った余りが 1 になることがわかりました。他の$n$について調べても似たような現象が確認されました。そこで次のような予想をしました。

$n=2^m, m\ge 2$で$p$が奇素数のとき、$p^{2n}+2^{np}$の素因数を$2^{m+2}$で割った余りは 1 である。

予想の証明

この予想を証明していきます。証明には高校数学の範囲を超えた知識を用いるのでご了承ください。

証明の鍵となるのは次の命題です。

互いに素な正の整数$a,b$に対して、$a^{2^n}+b^{2^n}$の 2 でない素因数を$q$とすると、$q\equiv 1\pmod{2^{n+1}}$が成り立つ。

$q$は素数で$a$を割り切らないので、$Aa\equiv 1\pmod{q}$をみたす整数$A$が存在する。このとき$(Ab)^{2^n}\equiv A^{2^n}b^{2^n}\equiv -A^{2^n}a^{2^n}\equiv -1\pmod{q}$となる。両辺を 2 乗して$(Ab)^{2^{n+1}}\equiv 1\pmod{q}$を得る。
ここで$Ab$の位数を$e$とする。すなわち$e$は$(Ab)^e\equiv 1\pmod{q}$となる最小の正の整数とする。$(Ab)^{2^{n+1}}\equiv 1\pmod{q}$だったので、位数の性質より$e$は$2^{n+1}$の約数である。もし$e=2^i, i\lt n+1$であったとすると、両辺を 2 乗することを繰り返して$(Ab)^{2^n}\equiv 1\pmod{q}$を得るが、$(Ab)^{2^n}\equiv -1\pmod{q}$であったので$1\equiv -1\pmod{q}$となる。これは$q$が奇素数であることと矛盾。よって$Ab$の位数は$2^{n+1}$である。
$Ab$と$q$は互いに素なので、フェルマーの小定理より$(Ab)^{q-1}\equiv 1\pmod{q}$が成り立つ。位数の性質より$q-1$は$2^{n+1}$で割り切れる。よって$q\equiv 1\pmod{2^{n+1}}$が得られた。

この命題を使いましょう。$p^{2n}+2^{np}=(p^2)^{2^m}+(2^p)^{2^m}$と表せます。$p$は奇素数なので$p^2,2^p$は互いに素です。よって次が得られました。

$n=2^m,m\ge 2$のとき、$p^{2n}+2^{np}$の素因数$q$は$q\equiv 1\pmod{2^{m+1}}$をみたす。

しかし証明したいのは$q\equiv 1\pmod{2^{m+2}}$でした。そのためには$p^{2n}+2^{np}$を$a^{2^{m+1}}+b^{2^{m+1}}$の形に表すことが必要です。第一項は$p^{2^{m+1}}$となるのでよいですが、第二項は$(2^p)^{2^m}$なので、$x^{2^{m+1}}$の形で表そうとすると、$x^2=2^p$をみたす必要があります。$p$は奇素数なのでこのような整数$x$は存在しません。

そこで方針を切り替えて、$x^2\equiv 2^p\pmod{q}$をみたす$x$を考えることにします。このために、平方剰余の概念を導入します。

$p$を奇素数、$a$を$p$と互いに素な整数とする。このとき
$$ \left(\frac{a}{p}\right)=\begin{cases} +1 & (x^2\equiv a\pmod{p}となる整数xが存在するとき) \\ -1 & (そうでないとき) \end{cases} $$
と定める。

証明したいのは$\left(\frac{2^p}{q}\right)=1$です。平方剰余の相互法則など様々な法則がありますが、実際に用いるのは次の 2 つです。

$p$を奇素数、$a,b$を$p$と互いに素な整数とすると、$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

第二補充法則

$p$を奇素数とするとき
$$ \left(\frac{2}{p}\right)=\begin{cases} +1 & (p\equiv 1,7\pmod{8}のとき) \\ -1 & (p\equiv 3,5\pmod{8}のとき) \end{cases} $$
が成り立つ。

第二補充法則を用いるためには$q$を 8 で割った余りが必要ですが、系より$q\equiv 1\pmod{2^{m+1}}$がわかっています。$m\ge 2$だったので、$q\equiv 1\pmod{8}$です。よって
$$ \left(\frac{2}{q}\right)=1 $$
となります。したがって
$$ \left(\frac{2^p}{q}\right)=\left(\frac{2}{q}\right)^p=1 $$
が得られました。すなわち$x^2\equiv 2^p\pmod{q}$をみたす整数$x$が存在します。これにより、予想を示すことができます。

予想は定理になった

$n=2^m, m\ge 2$で$p$が奇素数のとき、$p^{2n}+2^{np}$の素因数を$2^{m+2}$で割った余りは 1 である。

$p^{2n}+2^{np}$の素因数を$q$とする。$\left(\frac{2^p}{q}\right)=1$なので、$x^2\equiv 2^p\pmod{q}$をみたす整数$x$が存在する。さらにこの$x$を$p$と互いに素にできる。このとき$p^{2n}+2^{np}\equiv p^{2^{m+1}}+x^{2^{m+1}}\pmod{q}$となるので、$q$は$p^{2^{m+1}}+x^{2^{m+1}}$の素因数でもある。命題 3 より、$q\equiv 1\pmod{2^{m+2}}$を得る。