Maths Olympiad Prep

Library / /262 of 462

Number theory Difficulty 6.0 AIME, harder Prove it Ireland

Alice has written down an integer xx in decimal notation. Bob takes the first (left-most) digit of xx (which is not zero) and moves it to the far right, shifting all the other digits one space to the left. Alice remarks that the result of this operation is 3x3x. Find all possible values of xx.

Solution

Let the number of digits of xx be dd, the leading digit of xx be 1a91 \le a \le 9 and the remaining d1d-1 digits be 1b10d11 \le b \le 10^d - 1. There is no solution with d=1d=1, so we can assume d>1d > 1. Then the equations to solve are:
x=10d1a+b3x=10b+a \begin{align*} x &= 10^{d-1}a + b \\ 3x &= 10b + a \end{align*}
As 3x3x has the same number of digits as xx, the leading digit of xx must be a=1,2a = 1, 2 or 33. Eliminating xx, we obtain
a(310d11)=7b. a(3 \cdot 10^{d-1} - 1) = 7b.
As bb has d1d-1 digits, we have b<10d1b < 10^{d-1}, which gives (3a7)10d1<a(3a - 7)10^{d-1} < a. Because d>1d > 1 we can now exclude a=3a = 3, so we must have a=1a = 1 or a=2a = 2. As 1a31 \le a \le 3 it also follows that 77 divides 310d113 \cdot 10^{d-1} - 1, so that
10d310d11(mod7). 10^d \equiv 3 \cdot 10^{d-1} \equiv 1 \pmod{7}.
Checking powers of 10 (mod 7), we confirm that 10 is a primitive root and so 10d1(mod7)10^d \equiv 1 \pmod 7 if and only if d0(mod6)d \equiv 0 \pmod 6. So let us write d=6cd = 6c for an integer c>0c > 0, then solutions must take the form:
b=a7(3106c11)with c>0 and a{1,2}. b = \frac{a}{7} (3 \cdot 10^{6c-1} - 1) \quad \text{with } c > 0 \text{ and } a \in \{1, 2\}.
Adding the initial digit, we have:
x=106c1a+a7(3106c11)=a7(7106c1+3106c11)=a7(106c1)=106c1106110617a=106c11061142857a. \begin{align*} x &= 10^{6c-1}a + \frac{a}{7} (3 \cdot 10^{6c-1} - 1) \\ &= \frac{a}{7} (7 \cdot 10^{6c-1} + 3 \cdot 10^{6c-1} - 1) = \frac{a}{7} (10^{6c} - 1) \\ &= \frac{10^{6c} - 1}{10^6 - 1} \cdot \frac{10^6 - 1}{7} \cdot a = \frac{10^{6c} - 1}{10^6 - 1} \cdot 142857 \cdot a. \end{align*}
For any c1c \ge 1, we note that (106c1)/(10c1)=k=0c1106k(10^{6c} - 1)/(10^c - 1) = \sum_{k=0}^{c-1} 10^{6k} consists of cc ones, each separated by five zeros. Because 2142857=2857142 \cdot 142857 = 285714 the solutions to the problem are numbers of the following form:

142857 repeated cc times and 285714 repeated cc times, c1c \ge 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.