まず「有限個になるの！？」って見た目が面白かった！

問題へのリンク

問題

以下の条件をともにみたす正整数 $n$ の総和を求めてください：

$n$ 以下の正の整数であって、 $n$ を割った余りが $1$ であるものが、ちょうど $2$ 個存在する
$n$ 以下の正の整数であって、 $n$ を割った余りが $2$ であるものが、ちょうど $22$ 個存在する

考えたこと：条件の言い換え

問題文を見た瞬間に思ったのは「有限個になるの！？マジで！？」という感じでしたね。

なにはともあれ考察を深めていきましょう。まず、最初の条件を言い換えます。

正の整数 $x$ が $n$ を割った余りが $1$ である
$\Leftrightarrow$ $x \ge 2$ かつ $x$ は $n-1$ の約数である

となることから、最初の条件は「 $n-1$ の約数がちょうど $3$ 個である」と言い換えられます。 $n-1$ の約数は $1$ も含めると $2 + 1 = 3$ 個であるということです。

同様にして、後者の条件は、以下のいずれかに言い換えられます。

$n-2$ が偶数であるとき： $n-2$ の約数がちょうど $24$ 個 ( $1, 2$ も含める)
$n-2$ が奇数であるとき： $n-2$ の約数がちょうど $23$ 個 ( $1$ も含める)

素因数分解を元にした考察を進める

約数がちょうど 3 個である数とは、素数 $p$ を用いて $p^{2}$ と表せる数のことですね。よって、素数 $p$ を用いて

$n = p^{2} + 1$

と表せます。 $p = 2$ は明らかに後者の条件を満たさないので、 $p$ は奇素数です。よって、 $n-2$ は偶数にしかなりませんので、後者の条件は

「 $n-2$ の約数がちょうど $24$ 個」

となります。約数が $24$ 個という条件はなかなかに厄介ですね。要領よく探索したいところです。

さて、 $n = p^{2} + 1$ であることから、 $n-2 = (p+1)(p-1)$ と表せます。ここで、よくある議論ですが、次のことが言えます。

$p$ が奇数であるとき

$\mathrm{ord}_{2}(p+1) = 1, \mathrm{ord}_{2}(p+1) \ge 2$ であるか、 $\mathrm{ord}_{2}(p+1) \ge 2, \mathrm{ord}_{2}(p+1) = 1$ であるかのいずれかである
$\frac{p+1}{2}$ と $\frac{p-1}{2}$ は互いに素である

この先、これらの知見が大活躍します！

約数が 24 個という条件をうまく扱う

それでは、 $(p+1)(p-1)$ の約数が $24$ 個であるための条件を絞りましょう。

まず、上の議論から、 $(p+1)(p-1)$ は最低でも $2^{3}$ で割り切れることがわかります。このことから、次の場合に分けられます。ここで、 $q, r$ を素数としています。

Case 1： $(p+1)(p-1) = 2^{3} q^{5}$
Case 2： $(p+1)(p-1) = 2^{3} q^{2} r$
Case 3： $(p+1)(p-1) = 2^{5} q^{3}$
Case 4： $(p+1)(p-1) = 2^{5} qr$
Case 5： $(p+1)(p-1) = 2^{11} q$
Case 6： $(p+1)(p-1) = 2^{22}$

順に調べていきましょう。結構腕力を問われる問題ですね！

Case 1： $(p+1)(p-1) = 2^{3} q^{5}$

$\frac{p+1}{2}$ と $\frac{p-1}{2}$ が互いに素であることから、次の 4 パターンに分かれます。

$p+1 = 2^{2}q^{5}, p-1 = 2$
$p+1 = 2^{2}, p-1 = 2q^{5}$
$p+1 = 2q^{5}, p-1 = 2^{2}$
$p+1 = 2, p-1 = 2^{2}q^{5}$

$q \ge 3$ であることを踏まえると、いずれも不適です。

Case 3： $(p+1)(p-1) = 2^{5} q^{3}$

Case 2 は恐らく本命 (直観により) なので、先にダメそうな Case 3 を片付けることにしました。

実際、Case 1 とほぼ同様に不適であることがわかりました。

Case 5： $(p+1)(p-1) = 2^{11} q$

同様に不適です。

Case 6： $(p+1)(p-1) = 2^{22}$

明らかに不適です。

Case 4： $(p+1)(p-1) = 2^{5} qr$

Case 2, 4 が残ったのですが、Case 4 の方が対称性から楽できそうという理由から、先に Case 4 をやりました。

この場合は、次のいずれかになります。

$p + 1 = 2^{4}q, p - 1 = 2r$
$p + 1 = 2q, p - 1 = 2^{4}r$

ここで一瞬途方に暮れたのですが、「3 つの素数が式で結ばれている」という状況から、「 $p, q, r$ のいずれかは $3$ になるのではないか」という直観が働きました！

きちんと示しましょう。 $\mod 3$ で考えてみます。

$p = 3$ の場合は明らかに不適なので、 $p$ を $3$ で割った余りは $1$ または $2$ としてよいです。よって、 $p + 1, p - 1$ のいずれかは $3$ の倍数となります。

つまり、 $q = 3$ または $r = 3$ が成り立つのです！！！

それを踏まえて、 $p, q, r$ が素数になるパターンをすべて求めると、

$(p, q, r) = (47, 3, 23)$

が得られます。

Case 2： $(p+1)(p-1) = 2^{3} q^{2} r$

この場合は、次のいずれかになります。

$p + 1 = 2^{2}q^{2}, p - 1 = 2r$
$p + 1 = 2^{2}r, p - 1 = 2q^{2}$
$p + 1 = 2q^{2}, p - 1 = 2^{2}r$
$p + 1 = 2r, p - 1 = 2^{2}q^{2}$

パターンが増えましたが、Case 4 と同様に、 $p$ は $3$ ではないとしてよくて、 $q = 3$ または $r = 3$ となります。

$p, q, r$ が素数になるパターンをすべて求めると、

$\begin{align} (p, q, r) &= (37, 3, 19) \\ (p, q, r) &= (19, 3, 5) \end{align}$

が得られました。

まとめ

以上をまとめると、 $p = 19, 37, 47$ という $3$ 個の解があります。それぞれ、 $n = p^{2} + 1$ より、

$n = 362, 1370, 2210$

と求められます。答えは、この総和である $3942$ です！

感想

$q = 3$ または $r = 3$ が導かれる瞬間の快感はやばいですね！

個人的には次の問題を思い出しました。

$p, p + 2, p + 4$ がすべて素数となるような正の整数 $p$ の値をすべて求めよ。

これも $\mod 3$ で考えることで綺麗に解けます。

けんちょんの数学・情報・教育探検記

数学・情報・心理・教育など色々なことを書いていきます！

OMC 164 E 問題 (青色, 400 点)

問題