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。