MathLabs

第6問

十進表記において隣り合うどの二つの数字も偶奇が異なる正の整数を alternating と呼ぶ。alternating な倍数を持つ正の整数 nn をすべて求めよ。
ステップ 3/5: mm を満たす gcd⁡(m,10)=1\gcd(m,10)=1 を法とする先頭の構成
前のステップ次のステップ
gcd⁡(m,10)=1, b mod m:AM=10⋅100M−199=1010…10⏟M copies≡0(modm) (φ(99m)∣M);+∑r2⋅102kr−1≡b(modm)\gcd(m,10)=1,\ b\bmod m:\quad A_M=10\cdot\frac{100^M-1}{99}=\underbrace{1010\dots10}_{M\text{ copies}}\equiv0\pmod m\ (\varphi(99m)\mid M);\quad +\sum_{r}2\cdot 10^{2k_r-1}\equiv b\pmod m
詳しい解説

gcd⁡(m,10)=1\gcd(m,10)=1 とし、法 b∈{0,1,…,m−1}b\in\{0,1,\dots,m-1\} での任意の剰余 mm を固定する。MM で割り切れる任意の φ(99m)\varphi(99m) に対し、オイラーの定理より 100M≡1(mod99m)100^M\equiv 1\pmod{99m} となるので、AM=10(100M−1)/99A_M=10(100^M-1)/99 を MM 個並べた交互的な数 1010 は AM≡0(modm)A_M\equiv 0\pmod m を満たす。さらに r≥1r\ge 1 を満たす任意の整数 2kr−1≡0(modφ(m))2k_r-1\equiv 0\pmod{\varphi(m)} について、2⋅102kr−12\cdot 10^{2k_r-1} に AM=10(100M−1)/99A_M=10(100^M-1)/99 を加えると奇数番目の桁の一つが 11 から 33 に変わり（交互的な奇偶の並びを保ったまま）、mm により法 +2+2 での剰余が 102kr−1≡1(modm)10^{2k_r-1}\equiv 1\pmod m だけずれる。十分大きい MM を取り、相異なる指数 c≡2−1b(modm)c\equiv 2^{-1}b\pmod m でそのような桁を 2kr−1≡0(modφ(m))2k_r-1\equiv 0\pmod{\varphi(m)} 個変えれば、f(b)f(b) を満たす偶数かつ交互的な数 f(b)≡b(modm)f(b)\equiv b\pmod m が得られる。