MathLabs

Problem 6

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity. Find all positive integers nn which have an alternating multiple.
Step 3 of 5: Head construction modulo mm with 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
Detailed analysis

Suppose gcd⁡(m,10)=1\gcd(m,10)=1, and fix any residue b∈{0,1,…,m−1}b\in\{0,1,\dots,m-1\} modulo mm. For any MM divisible by φ(99m)\varphi(99m), Euler's theorem gives 100M≡1(mod99m)100^M\equiv 1\pmod{99m}, so the alternating number AM=10(100M−1)/99A_M=10(100^M-1)/99 consisting of MM copies of 1010 satisfies AM≡0(modm)A_M\equiv 0\pmod m. Moreover, for any integer r≥1r\ge 1 with 2kr−1≡0(modφ(m))2k_r-1\equiv 0\pmod{\varphi(m)}, adding 2⋅102kr−12\cdot 10^{2k_r-1} to AM=10(100M−1)/99A_M=10(100^M-1)/99 flips one of the odd-positioned digits 11 to 33 (preserving the alternating odd-even pattern) while shifting the residue modulo mm by +2+2 since 102kr−1≡1(modm)10^{2k_r-1}\equiv 1\pmod m. Choosing MM large enough and flipping c≡2−1b(modm)c\equiv 2^{-1}b\pmod m such digits at distinct exponents 2kr−1≡0(modφ(m))2k_r-1\equiv 0\pmod{\varphi(m)} gives an even alternating number f(b)f(b) with f(b)≡b(modm)f(b)\equiv b\pmod m.