創作整数問題#30解法&創作整数問題#31


明けましておめでとうございます。今年も忙しい日が続いてしまうと思いますが、ブログもホームページもこまめに更新していきたいと思います。

とはいうものの、今年の抱負なんて1ヶ月も経たないうちに忘れてしまいますよね・・・。掛け軸にでもして飾っておけば良いのでしょうか(笑)?


《問題#31》

十進法表記における$n^3$の各位の数の和が$n$に等しくなるような正の整数$n$のうち、$3$の倍数であるものをすべて求めよ。

(創作問題)


まずは候補の絞り込みですね。なお「$3$の倍数」という制約を外せば、そのような$n$は全部で6個存在します。

 

 

 

» 答えはこちら

答えは $\color{red}{n=18、27}$ です。

» 閉じる


創作整数問題#30(解き方)


$2015^{2016}+2016^{2015}$は素数か。

今回の問題は西暦に関係する出題でした。過去にも創作整数問題#1創作整数問題#18で$2017$という数字が登場していますが、西暦や年号を使った出題というのはそれほど珍しくはありません。数学オリンピックなんかを見ても西暦の数字をちらほら見かけますし、入試問題にも散見されますよね。去年の西暦である$2017$は素数であるため、整数問題においては何かと使いやすい数字だったと言えます(因みに$2017$は$306$番目の素数です)。

さて、今回の創作整数問題#30は一見して、西暦に関する問題であることが見て取れると思います。問題文中には直接出てきていませんが、$2017$が素数であることに注目出来れば、指数タイプの整数分野の必須技巧である「フェルマーの小定理」が利用できることに気付くことができます。ここではより一般的な場合からアプローチする解き方を示しておきます。


《解答例》

より一般の場合を考え、$a_n=n^{n+1}+(n+1)^n$ と置いて、素数$p$に対して$a_{p-2}$が$p$で割り切れることを示す。

$a_{p-2}=(p-2)^{p-1}+(p-1)^{p-2}$ の両辺に $(p-2)(p-1)^2$ を乗じると、$$(p-2)(p-1)^2 a_{p-2}=(p-2)^{p}(p-1)^2+(p-2)(p-1)^{p}$$となる。ここでフェルマーの小定理より、右辺について$$\begin{align}&\ \ \ \ \ (p-2)^{p}(p-1)^2+(p-2)(p-1)^{p} \\ &\equiv (p-2)(p-1)^2+(p-2)(p-1) \pmod{p} \end{align}$$であり、$$\begin{align}&\ \ \ \ \ (p-2)(p-1)^2+(p-2)(p-1) \\ &=(p-2)(p-1)\{(p-1)+1\} \\ &=p(p-1)(p-2) \end{align}$$である。故に$$(p-2)(p-1)^2 a_{p-2} \equiv p(p-1)(p-2) \pmod{p}$$となるが、$p$、$p-1$、$p-2$ はいずれも互いに素であるから$$a_{p-2} \equiv p \equiv 0 \pmod{p}$$となり、これより$a_{p-2}$は$p$の倍数であることが分かる。したがって素数$p$に対して$a_{p-2}$が$p$で割り切れることが示された。

上記の結果より、$a_{2015}=2015^{2016}+2016^{2015}$ は素数$2017$で割り切れることが分かるので、$2015^{2016}+2016^{2015}$は素数ではない(合成数である)。


恐らく具体値で考えても埒が明かないのではないかと思います。本問のように西暦の数字など、数字の選び方に関して何となく一種の任意性(arbitrariness)が嗅ぎ取れる問題では、より一般的な場合の証明から入ると上手くいくことがあります。実際、こういった手法は数学コンテストなどでもかなり有用です。

また、創作整数問題#22のように文字の制約が少なく、条件が一般的な形で与えられている場合は、逆に特殊なケースを考えてみることで何かしらのヒントが得られる場合もあります。

但しいずれの方針も絶対的なものではなく、解答の際は臨機応変に対応しなければなりませんが、そこが数学の醍醐味でもあります。試行錯誤の過程を楽しめてこそ数学愛好家と言うべきでしょう!

 

●  ●  ●  ●  ●

 

今回もおまけ問題があります(笑)。というのも、2012年の中国西部数学オリンピックに以下のような問題が出題されているのです。


《おまけ問題》

任意の奇素数$p$について、$a_n=n^{n+1}+(n+1)^n$ が$p$で割り切れるような正の整数$n$が無数に存在することを示せ。

(2012年中国西部数学MO 第8問)


どうやって証明すべきか考える訳ですが、意外にあっさりと解決できてしまいます。単純に$n$にある式を代入すれば良いのですが、皆さん気付いたでしょうか?

 

 

» おまけ問題の答えはこちら

$n$に $\color{red}{(pm+1)(p-1)-1 \ (m \in \mathbb{Z} \geqq 0)}$ を代入すれば$a_n$は奇素数$p$で割り切れます。

» 閉じる

 


おまけ問題に関連して余談を一つ。

実は$a_n$の剰余には周期性があります。例えば $n=6N+1$ 型のとき$a_n$は$3$で割り切れ、$n=20N+\color{blue}{3} \ \text{or}\ \color{blue}{6}$ 型のとき$a_n$は$5$で割り切れ、$n=42N+\color{blue}{5} \ \text{or}\ \color{blue}{25} \ \text{or}\ \color{blue}{26} \ \text{or}\ \color{blue}{37}$ 型のとき$a_n$は$7$で割り切れます。さらに、$r=7$、$9$、$28$、$45$、$62$、$68$、$83$、$96$ とすれば、$n$が $110N+r$ 型の整数であるとき$a_n$は$11$で割り切れます。

このように素数$p$について、$a_n$が$p$の倍数となるような$n$には $p(p-1)$ の周期が存在し、また多くの場合、余り$r$が複数存在します。おまけ問題の答えとして提示した式はあくまでも「こうすれば無数の値が構成できる」という方法でしかなく、すべてのパターンを網羅している訳ではありません。

そもそもこの創作整数問題#30は、どんな$n$のときに $n^{n+1}+(n+1)^n$ が素数となるのかについて調べているなかで発想されたものです。プログラムによれば、$n \leqq 100$ の範囲では$a_1$、$a_2$、$a_{80}$が素数であることが分かりましたが、残念ながらマイPCでは $a_{93}$ の素因数分解ができませんでした。恐らく非常に大きな素因数をもつものと思われます。

実際には $n=1$、$2$、$80$、$342$、$848$、$1194$、$2658$、$4790$、$9376$、$\cdots$ のときに、本問の$a_n$である $n^{n+1}+(n+1)^n$ が素数になることが知られています(Cf.オンライン整数列大辞典の数列:A073499)。桁数が大きい$a_n$は、数値を求める計算ならばともかく、その素因数分解は困難を極めます。$9376^{9377}+9377^{9376}$ に至っては桁数が何と$37246$桁に上り、10万ビットを超える整数となりますから、その素因数分解はスーパーコンピュータでも難しいと言えます。


(コメント)

$a_n$を割り切るような正の整数$n$を $n=p(p-1)N+r$ と表示するとき、各奇素数$p$に対して何個の$r$が対応するのかについては、まだまだ考察の余地がありそうですね!

 

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です