続き

前回の平方コピペ数解答 - ange1のブログで、答えは出たわけですが、ちょっと気になるところが出てきました。

件の数は11桁の繰り返し ( 22桁 ) の数で、$10^{11}+1$ の素因数11の指数が2という性質があったのですが。この11桁、素因数11 ( おや同じ11でもありますね!! ) はどうして出てきたのでしょうか…?

特に、余りの取りうる値の範囲の広さを考えると、11よりも7の方が先に引っかかるんじゃないの?? 11になったのは偶然?? というところが気になったので調べてみました。
※こうやって記事にする以上、偶然ではない何かがあったわけなのですが、まあ結論は後をお楽しみに? ということで

問題の整理

今回の問題の肝は、

$10^n+1$が、指数2以上の素因数を持つような最小の$n$と、その時の素因数$p$ ( 指数も ) を求める

という所でした。これを一般化すると、

$a^n\equiv -1\,\, mod\,p^2$ の解$(n,p)$を求める

ということに他なりません。なお、$a\equiv 0\,\,mod\,p$ や $a\equiv 1\,\,mod\,p\,( p\neq 2 )$だと解なしになるので除外しておきます。元の問題では、$p=2,3,5$ が該当します。

位数

さて、素数$p$に関しては有名なフェルマーの小定理

$a^{p-1}\equiv 1\,\,mod\,p$

というのがあり $mod\,p$の世界は、乗法において閉じた有限要素数の群 ( 有限群 ) となることが知られています。

ここで適当な$g$を選ぶことで、$g^0,g^1,g^2,\cdots,g^{p-1}$ が$1\sim p-1$を全てカバーすることができるのですが ( こういう$g$を生成元だとか、有限体の話だと原始元だと言いますね )、一般の$a$でどうかというとそうとは限りません。
すなわち、

$a^d\equiv 1\,\,mod\,p$ を満たす最小の正の整数 $d$ に対して、$d\le p-1$ ではあるものの$d=p-1$とは限らない

ということです。この$d$のことを位数と言います。なお、$d$は$p-1$の約数となります。

本題

ここから本題に入ります。

位数$d$とは、$a^d\equiv 1\,\,mod\,p$を満たす最小の正の整数である

加えて、$a\not\equiv 1\,\,mod\,p$ ですから、$d\ge 2$です。かつ、$d=2$となるのは$a\equiv -1\,\,mod\,p$に限られます。

それでは$mod\,p^2$ではどうなのでしょうか…?

$a^m\equiv 1\,\,mod\,p^2\Rightarrow a^m\equiv 1\,\,mod\,p$ですから、$m $が$d$の倍数であることが必要。
そして、$a^d\equiv pq+1\,\,mod\,p^2,\,\,m=dk$ と置いたとき、

$$ \begin{eqnarray} a^m&\equiv&a^{dk} \\ &\equiv&(qp+1)^k \\ &\equiv&1+kqp+{}_kC_2q^2p^2+{}_kC_3q^3p^3+\cdots \\ &\equiv&1+kqp\,\,(\,全て\,\,mod\,p^2 ) \end{eqnarray} \\ \therefore a^m\equiv 1\,\,mod\,p^2\Leftrightarrow kqp\equiv 0\,\,mod\,p^2\Leftrightarrow kq\equiv 0\,\,mod\,p $$

pは素数ですから、結局 $k\equiv 0\,\,mod\,p$
ということで、$mod\,p^2$においては、$a$の位数は$dp$となります。すなわち

$a^m\equiv 1\,\,mod\,p^2$を満たす最小の正の整数$m $は$m=dp$
※ここには重大な突っ込み所があります!! が一旦このまま進めます。

さてしかし、今回の問題で欲しいのは$a^n\equiv -1\,\,mod\,p^2$でした。1ではなく-1です。…ところがこの-1というのはmodの世界であっても平方根ですので、指数としては半分、$n=\frac{m}{2}=\frac{dp}{2}$で済むのですね。これは$m $の最小性を利用して示すことができます。( なお、$m $が奇数の場合は解なしです )

これで条件が整いました。

$a$の$mod\,p$における位数$d\,( d\ge 2 )$に対して、$d$が偶数の時に限り$a^n\equiv -1\,\,mod\,p^2$を満たす最小の$n$が存在し$n=\frac{dp}{2}$
※突っ込み所は依然残っています!!

では元の問題に戻って$a=10$のケースで考えると、ちょうど$p=11$のとき$a\equiv -1\,\,mod\,p$、位数2に該当するので$n=\frac{2\times 11}{2}=11$です。
唯一の対抗馬の$p=7$の場合位数6ですから、$n=\frac{6\times 7}{2}=21$。これより小さい$n$で済み、$n$の最小値11、その時の$p$も11とすぐわかるわけです。

突っ込み所

$n,p$が分かってめでたしめでたし…と言いたいところですが、上の話には重大な穴があります。それは次のところ、

そして、$a^d\equiv pq+1\,\,mod\,p^2,\,\,m=dk$ と置いたとき、

この時に$q\equiv 0\,\,mod\,p$の可能性を考えてないことです。

pは素数ですから、結局 $k\equiv 0\,\,mod\,p$
ということで、$mod\,p^2$においては、$a$の位数は$dp$となります。すなわち

この部分、$q\equiv 0\,\,mod\,p$では成立しません。実際、$p=487$に対して$a=10$の位数486、$10^{486}\equiv 1\,\,mod\,487^2$ という例がありますので考慮不足ということになります。

…ということで、$(n,p)=(11,11)$が解になるのは確かではありますが、$n\lt 11$のケースについては個別に確かめざるを得ません。最小性はtrivialではない、ということでした。

終わりに

とは言え、実際に答えにすぐ辿り着ける訳ですから面白いところです。会場でコレ一発で解いてたらファインマンさんめいて爽快だったでしょうね。