Maths Olympiad Prep

Library / IRL ABooklet /97 of 191

IRL ABooklet

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 1≤a≤91 \le a \le 9 and the remaining d−1d-1 digits be 1≤b≤10d−11 \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=10d−1a+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(3⋅10d−1−1)=7b. a(3 \cdot 10^{d-1} - 1) = 7b.
As bb has d−1d-1 digits, we have b<10d−1b < 10^{d-1}, which gives (3a−7)10d−1<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 1≤a≤31 \le a \le 3 it also follows that 77 divides 3⋅10d−1−13 \cdot 10^{d-1} - 1, so that
10d≡3⋅10d−1≡1(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 10d≡1(mod7)10^d \equiv 1 \pmod 7 if and only if d≡0(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(3⋅106c−1−1)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=106c−1a+a7(3⋅106c−1−1)=a7(7⋅106c−1+3⋅106c−1−1)=a7(106c−1)=106c−1106−1⋅106−17⋅a=106c−1106−1⋅142857⋅a. \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 c≥1c \ge 1, we note that (106c−1)/(10c−1)=∑k=0c−1106k(10^{6c} - 1)/(10^c - 1) = \sum_{k=0}^{c-1} 10^{6k} consists of cc ones, each separated by five zeros. Because 2⋅142857=2857142 \cdot 142857 = 285714 the solutions to the problem are numbers of the following form:

142857 repeated cc times and 285714 repeated cc times, c≥1c \ge 1.

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

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