# 2004 IMO Problems/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 $n$ which have an alternating multiple.

## Solution

We claim that all positive integers $n$ except multiples of $20$ have a multiple that is alternating. If $n$ is a multiple of $20$, then the units digit is $0$ and the tens digit is a multiple of $2$, so both digits are even. Now, we will prove that if $20\nmid n$, then there is a multiple of $n$ that is alternating.

We claim that there exists a $2k$ digit alternating integer that is a multiple of $2^{2k+1}$ and there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$. We will prove this by induction.

Base Case: $k=1$ We can let the number be $16$.

Inductive Step: Let $a$ be a $2k-2$ digit alternating number such that $2^{2k-1}\mid a$. Since $a$ is even, this means that the first digit of $a$ is odd. Let $b\cdot2^{2k-1}\equiv a\pmod{2^{2k+1}}$, where $b\in\{0,1,2,3\}$. Let $x=16-2b$. We see that $x$ is alternating, so the number $x\cdot10^{2k-2}+a$ is also alternating. We also have $x\equiv-2b\pmod8$. Since $a\equiv b\cdot2^{2k-1}\pmod{2^{2k+1}}$, this means that we have \begin{align*} x\cdot10^{2k-2}+a&\equiv x\cdot10^{2k-2}+b\cdot2^{2k-1}\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(x\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(-2b\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv -b\cdot2^{2k-1}\left(5^{2k-2}-1\right)\pmod{2^{2k+1}}.\end{align*} Since $4\mid5^{2k-2}-1$, this means that $x\cdot10^{2k-2}+a\equiv0\pmod{2^{2k+1}}$, so $x\cdot10^{2k-2}+a$ is a $2k$ digit alternating number that is a multiple of $2^{2k+1}$.

Now, we will prove that there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$.

Base Case: $k=1$ We can let the number be $0$.

Inductive Step: Let $a$ be a $k-1$ digit alternating number such that $2\cdot5^{k-1}\mid a$. Let $S$ be the set of digits such that $x\cdot10^{k-1}+a$ is alternating. We see that either $S=\{0,2,4,6,8\}$ or $S=\{1,3,5,7,9\}$. In each possible set, each $\mod5$ residue appears exactly once. Let $a=2\cdot5^{k-1}\cdot b$. Then, $x\cdot10^{k-1}+a=2\cdot5^{k-1}\left(x\cdot2^{k-2}+b\right)$. Therefore, there exists an $x$ such that $2\cdot5^k\mid x\cdot10^{k-1}+a$, so there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$. If $k$ is even, then $0\not\in S$, so it has exactly $k$ digits.

Now, let $n=2^a\cdot5^b\cdot m$. Then, if $20\nmid n$, then $a<2$ or $b=0$. If $b=0$, then there exists a $2a$ digit alternating integer $x$ that is a multiple of $2^{2a+1}$. Consider the sequence $a_i=x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$. Then, the decimal representation of $a_i$ is the result when $x$ is written $i$ times. For any prime $p$ that divides $n$, if $p\mid10^{2a}-1$, then $\nu_p\left(10^{2ai}-1\right)=\nu_p\left(10^{2a}-1\right)+\nu_p(i)$, so $\nu_p(a_i)=\nu_p(x)+\nu_p(i)\geq\nu_p(i)$. Therefore, there exists an $i$ such that $p^{\nu_p(n)}\mid a_{ci}$ for all $c$. If $p\nmid10^{2a}-1$, then if $i=\phi(n)$, then $p^{\nu_p(n)}\mid10^{2ai}-1$ if $p\neq2,5$. Since $5\nmid n$, this means that we only need to make sure $2^a\mid x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$. Since $2^{2a+1}\mid x$, this means that this is true, so if $5\nmid n$, then there exists a multiple of $n$ that is alternating.

If $a<2$, then there exists an alternating integer $x$ with exactly $2b$ digits that is a multiple of $2\cdot5^{2b}$. Then, the first digit of $x$ is odd. Let $a_i=x\cdot\frac{10^{2bi}-1}{10^{2b}-1}$. Then, if $p\mid10^{2b}-1$, then $\nu_p(a_i)\geq\nu_p(i)$, so there exists an $i$ such that $p^{\nu_p(n)}\mid a_i$. If $p\nmid10^{2a}-1$, then we can let $i=\phi(n)$, so $p^{\nu_p(n)}\mid a_i$. If $p=5$, then $5^b\mid5^{2b}\mid x$, and if $p=2$, then $a=0,1$, so $p^a\mid x$. Therefore, $n\mid a_i$ for some $i$.

Therefore, all positive integers except multiples of $20$ have an alternating multiple.