n^16-n^4を割り切る数

127

問題　～今回は比較的軽い出題です～

　$n^{16}-n^4\equiv 0\;\;({\rm mod}\;2^{16}-2^4)$を示せ。

本問は UC Berkeley Preliminary Exam (Spring 1990, Problem 16)で出題されたものの拡張になっている。とはいえ、作問時(高校2年生当時)にはそんなことを知らず、つい数日前に先行研究(？)を発見した次第である。

解答　～フェルマーさんに多大なる感謝を～

　フェルマーの小定理より、任意の$n\in \mathbb{N}$に対して$n^p-n\equiv0\;\;({\rm mod}\;p)$が成り立つ(ただし$p$は素数)。

$$\begin{eqnarray} n^{16}-n^4&=&(n^5-n)(n^{11}+n^7+n^3)\\&=&(n^7-n)(n^9+n^3)\\&=&(n^{13}-n)n^3 \end{eqnarray}$$

であるから、$n^{16}-n^4\equiv 0\;\;({\rm mod}\;5\cdot 7\cdot 13)$となる。
　また、任意の$m\in \mathbb{N}$に対して$(2m)^4=2^4 m^4\equiv0\;\;({\rm mod}\;2^4)$かつ$(2m+1)^4=2^4 m^2 (m+1)^2+2^3 m(m+1)+1\equiv1\;\;({\rm mod}\;2^4)$なので($\because$連続$2$整数の積は$2$の倍数)、
$n=2m$のとき$n^{16}-n^4=\left((2m)^4\right)^4-(2m)^4\equiv 0^4-0=0\;\;({\rm mod}\;2^4)$、
$n=2m+1$のとき$n^{16}-n^4=\left((2m+1)^4\right)^4-(2m+1)^4\equiv 1^4-1=0\;\;({\rm mod}\;2^4)$
であり、結局任意の$n\in \mathbb{N}$に対して$n^{16}-n^4\equiv 0\;\;({\rm mod}\;2^4)$とわかる。
　${\rm mod}\;2^4$の場合と同様に考えると$n^{16}-n^4\equiv 0\;\;({\rm mod}\;3^2)$も判明するので、ここまでの議論を統合して$n^{16}-n^4\equiv 0\;\;({\rm mod}\;2^4\cdot3^2\cdot5\cdot7\cdot13)$となる。$2^4\cdot3^2\cdot5\cdot7\cdot13=65520=2^{16}-2^4$であるから示された。

あとがき　～別名：考察の丸投げ～

　$a,b\in \mathbb{N},\;a>b$とし、$f(n)=n^a-n^b$と定める。また、任意の$n\in \mathbb{N}$に対して$f(n)\equiv 0\;\;({\rm mod}\;f(2))$となるような$(a,b)$の集合を$X$とする。このとき、$X$の要素にはどんな法則性があるだろうか。
　具体的に要素を列挙すると、$(2,1),(3,1),(4,2),(5,1),(5,3),(6,2),(7,3),(8,2),(8,4),(9,3),(14,2),(15,3),(16,4)$がある。つまり、上の問題は筆者の知っている$(a,b)$の組の中で最大のものである。この13個以外に$X$の要素が存在するかどうか、筆者は無いと予想しているが、未だ解決していない。誰か心優しいお方が現れて、解決策を提示してくださることを期待する。

　追記(2022/05/02)： kkkaaa さんが上記の予想を証明してくださいました。8ヶ月前に。更新が遅れてしまい申し訳ございません……。証明はこちらから読めます。

投稿日：2021年3月31日