10^2013-1の100以下の約数(JMO2013yo9)

twitterで見かけて書きたくなったので, ${10}^{2013}-1$の$100$以下の正の約数の個数を求めてみます. (ちなみに JMO2013yo9 の問題です.)

$N={10}^{2013}-1$としましょう. まず明らかに偶数は約数にはなりません. 次に明らかに$N$は$9$で割り切れます. これについて少し考えればLTEの補題から$v_3({10}^{2013}-1)=v_3(100-1)+v_3(2013)=3$なので$N$は$27$は約数だけど$81$は約数に持たないことが分かります.

さて, $3$以外の素因数を持つ場合を考えましょう. とりあえず$p>3$を素数として$p|N$としましょう. まず明らかに$p\ne 5$. そしてフェルマーの小定理より${10}^{p-1}\equiv 1\equiv {10}^{2013}(\mathrm{mod}p)$となるので$1\equiv {10}^{gcd(p-1,2013)}(\mathrm{mod}p)$. ここで$2013=3\cdot 11\cdot 61$であるので$gcd(p-1,2013)$は$1,3,11,33,61$を取り得ます. $61|p-1$とすると$p-1$が偶数である事と合わせて$p-1\ge 122$となって矛盾するので$g=gcd(p-1,2013)=1,3,11,33$を考えれば十分です.

$g=1$のとき$p|9$. $p>5$に矛盾.

$g=3$のとき$p|999$かつ$3|p-1$. これを満たすのは$p=37$.

$g=11$のとき$p|{10}^{11}-1$かつ$11|p-1$. 二つ目の条件から$p=23,67,89$.
ここから絞るのに工夫をします. $p=23,89$のとき条件から${10}^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$が成立します. これは$\left({\displaystyle \frac{10}{p}}\right)=1$を意味します. (オイラーの基準)
ここから平方剰余の諸法則より$\left({\displaystyle \frac{10}{23}}\right)=(-1{)}^{\frac{{23}^2-1}{8}}(-1{)}^{\frac{23-1}{2}\frac{5-1}{2}}\left({\displaystyle \frac{23}{5}}\right)=-1$, $\left({\displaystyle \frac{10}{89}}\right)=(-1{)}^{\frac{{89}^2-1}{8}}(-1{)}^{\frac{89-1}{2}\frac{5-1}{2}}\left({\displaystyle \frac{89}{5}}\right)=1$となります. とりあえず$23$は消せたけど$89$が残った. もう少し工夫しよう(別に普通に割り算すれば良いがつまらないので工夫する)${\displaystyle \frac{1}{10}}\equiv 9(\mathrm{mod}89)$より${10}^{11}\equiv 1(\mathrm{mod}89)\iff 3^{22}\equiv 1(\mathrm{mod}89)$である. よってオイラーの基準から$\left({\displaystyle \frac{3}{89}}\right)=1$. ここで平方剰余の相互法則から$\left({\displaystyle \frac{3}{89}}\right)=\left({\displaystyle \frac{89}{3}}\right)=-1$よって矛盾.
$67$は$g=33$で検討する.
$g=33$のとき. $p|{10}^{33}-1$かつ$33|p-1$. 二つ目の条件から$p=67$. これが一つ目の条件を満たせば良い. ここでオイラーの基準よりこれは$\left({\displaystyle \frac{10}{67}}\right)=1$と同値. そして$\left({\displaystyle \frac{10}{67}}\right)=(-1{)}^{\frac{{67}^2-1}{8}}(-1{)}^{\frac{5-1}{2}\frac{67-1}{2}}\left({\displaystyle \frac{2}{5}}\right)=1$となるので$67|N$が分かった.

これで素因数の情報が分かったのでそこから約数を列挙すると$d=1,3,9,27,37,67$. (素因数の情報からだけでは約数を列挙できるとは限らないが今回は$100$以下の約数に限定されていたため$p^2$型の約数が$9$しかないので助かった)

さて, 今年は$2023$年なので$M={10}^{2023}-1$でもやってみましょう.
まず$M$の約数は奇数. 次にLTEの補題より$v_3(M)=2$. $M$は$5$で割り切れず, $p>5$かつ$p|M$とする.
フェルマーの小定理より${10}^{gcd(p-1,2023)}=1(\mathrm{mod}p)$である. ここで$2023=7\cdot {17}^2$ を思い出しながら$p-1$が偶数であることに感銘を受けると$g=gcd(p-1,2023)=1,7,17$がわかる.

$g=1$のとき.　むり.
$g=7$のとき. $p=29,43,71$かつ$p|{10}^7-1$. とりあえず必要条件として$\left({\displaystyle \frac{10}{p}}\right)=1$. それぞれ計算すると$p=43,71$が残る. ここは諦めて割ってみるしかない. そしたらどれも条件を満たさない.
$g=17$のとき. そもそも条件を満たす$p$がない.
よって$d=1,3,9$のみ. さみしい.