Find all positive integers $n$ for which there exist two distinct numbers of $n$ digits, $\overline{a_1a_2\ldots a_n}$ and $\overline{b_1b_2\ldots b_n}$, such that the number of $2n$ digits $\overline{a_1a_2\ldots a_nb_1b_2\ldots b_n}$ is divisible by $\overline{b_1b_2\ldots b_na_1a_2\ldots a_n}$.
Problem
Source: Olimpiada Rioplatense 2013 Level 3, Problem 5.
Tags: number theory, greatest common divisor, modular arithmetic, algorithm, number theory proposed
07.08.2014 18:27
Let $A=\overline{a_1a_2 \ldots a_n}$ and $B=\overline{b_1b_2 \ldots b_n}$. According to the given conditions $A$ and $B$ are distinct $n$-digit positive integers, i.e. $(1) \;\; 10^{n-1} \leq A,B < 10^n$, and $\overline{a_1a_2 \ldots a_nb_1b_2 \ldots s b_n} = 10^nA + B$ is divisible by $\overline{b_1b_2 \ldots b_na_1a_2 \ldots a_n} = 10^nB + A$, i.e. $(2) \;\; 10^nA + B = k(10^nB + A)$ for positive integer $k$. Observe that $k=1$ implies the contradition $A=B$ and ${\textstyle k=\frac{10^nA+B}{10^nB+A}<10}$ since the both the numerator and the denominator are $2n$-digit numbers by (1). In other words, $2 \leq n \leq 9$. Equation (2) can be expressed as $(3) \;\; (10^n-k)A = (10^nk - 1)B$. Let $d=GCD(10^n-k, 10^nk-1)$. Hence ${\textstyle GCD(\frac{10^n-k}{d}, \frac{10^nk-1}{d})=1}$, which according to (3) means ${\textstyle \frac{10^nk-1}{d}|A}$, which give us ${{\textstyle A \geq \frac{10^nk-1}{d}}}$. Thus $10^nk - 1 \leq dA < d10^n$, yielding $k \leq d$, which implies $d \geq 2$ since $k > 1$. Futhermore $10^n \equiv k \pmod{d}$, yielding $0 \equiv 10^nk - 1 \equiv k^2 - 1 \pmod{d}$, i.e. $(4) \;\; d|(k-1)(k+1)$. We know that $d$ has a prime divisor $p$ since $d>1$. According to (4) we have $p|k \pm 1$, yielding $p \leq k+1 \leq 10$. Obviously $p \not \in \{2,5\}$ since $p|10^nk-1$. Thus $p \in \{3,7\}$. If $p=3$, then $p^2 \!\!\! \not | \, d$ since $9|10^nk-1$ implies $9|k-1$, which is impossible since $2 \leq k \leq 9$. Next assume $7 \!\!\! \not | \, d$. Then $d=3$ is the only possility. Also, since $2 \leq k \leq 3=d$ and $3|k \pm 1$, we have $k=2$. Therefore $0 \equiv 10^nk-1 = 2 \cdot 10^n - 1 \equiv 2 \cdot 1^n - 1 = 1 \pmod{3}$. This contradiction implies $7|d$. By the Division algorithm there exist two non-negative integers $q$ and $r<6$ s.t. $n=6q+r$. Hence $10^n = 10^{6q+r} = 10^r \cdot (10^6)^q \equiv 10^r \cdot 1^q \equiv 10^r \pmod{7}$ by Fermat's little theorem. Combining this with $7|GCD(10^n-k, 10^nk-1)=d$ we obtain $7|10^r-k$ and $7|10^rk-1$. Moreover $7|k \pm 1$, yielding $k \in \{6,8\}$ since $2 \leq k \leq 9$. Lets consider these two cases: Case 1: $k=6$. Then $7|10^r-6$ and $7|6 \cdot 10^r-1$ iff $r=3$. Thus, when $n \equiv 3 \pmod{6}$, the integers ${\textstyle A=\frac{6 \cdot 10^n - 1}{7}}$ and ${\textstyle B=\frac{10^n - 6}{7}}$ satisfies the conditions (1)-(2). Case 2: $k=8$. Then $7|10^r-8$ and $7|8 \cdot 10^r-1$ iff $r=0$. Furthermore $d|10^r-8$ and $10^r - 8 \equiv 1^r - 8 = -7 \equiv 2 \pmod{3}$ implies $3 \!\!\! \not | \, d$. This combined with $d | k^2 - 1 = 8^2 - 1 = 63 = 3^2 \cdot 7$ give us $d|7$. Consequently $d=7$ since $7|d$, which is impossible since $d \geq k=8$. Hence there are no integers $A$ and $B$ satisfying (1)-(2) in this case. Conclusion: There exist two integers $A$ and $B$ satisfying the conditions (1)-(2) iff $n \equiv 3 \pmod{6}$.