2015年の九州大学理系の第5問の素数が絡んだ整数問題です。
実際には誘導付きの問題ですが、誘導部分は最後のワンポイントでご紹介します。
問題
$p,q$ を異なる素数とする. $2^{p-1}-1=pq^2$ を満たす $p,q$ の組をすべて求めよ.
2015年九州大学理系第5問(3)より
解答
$p=2$ のとき
$2^{p-1}-1=1 $ であるが、$pq^2>1$ より不適。
$p\geq 3$ のとき
このような素数は奇数なので、自然数 $n$ を用いて、$p=2n+1$ と表せる。
このとき、
$$2^{p-1}-1=4^n-1\equiv 1^n-1=0\mod 3$$
である。よって、
$$pq^2\equiv 0\mod 3$$
となり、$p=3$ または $q=3$ であるとわかる。
(i) $p=3$ のとき
$2^{p-1}-1=3=3q^2$ となり、$q$ は素数であることに矛盾するので不適。
(ii) $p\neq 3$ のとき
$q=3$ となるので、
$$2^{p-1}-1=9p$$
$$(2^n-1)(2^n+1)=9p$$
である。また、自然数 $m$ が $m>1$ のとき、
$$2^n-1\equiv 2^n+1\mod m$$
とすると、$2\equiv 0\mod m$ となるので、$m=2$ である。
しかし、$9p$ が素数であるので、$2^n-1$ と $2^n+1$ は互いに素である。
また、$9p>2$ より、$2^n-1=1$ ではない。よって、
$$(2^n-1,2^n+1)=(9,p),(p,9)$$
である、
$2^n-1=9$ のとき、$2^n=10$ となり不適。
$2^n+1=9$ のとき、$n=3,p=7$ が得られる。
よって、求める組は $(p,q)=(7,3)$ である。
ワンポイント
この問題の誘導部分は、「$2^n-1$ と $2^n+1$ は互いに素であることを示せ」というものでした。
(ii) の因数分解を見つけることができるかがポイントです。
