Can You Shuffle Numbers?

A FiveThirtyEight Riddler puzzle.

By Vamshi Jandhyala in mathematics Riddler

March 23, 2018

Riddler Classic

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)

Solution

Let the last digit of our mystery number be $a$, and the rest of it be $b$. So the number we’re searching for equals $10b+a$. Let $b$ be an $n$-digit number. Then, moving the last digit to the front gives a new number equal to $10n \cdot a + b = 2(10b+a$).

Simplifying that gives $(10^n−2)a=19b$. For $a$ and $b$ to be integers, we need the left-hand side to be divisible by $19$, like the right-hand side is. In other words, we need it to be the case that $10^n=2$ mod $19$.

From Little Fermat’s Theorem we have

$$ \begin{align*} 10^{18} & \equiv 1\ (\textrm{mod}\ 19) \
\implies 2 \cdot 10^{18} &\equiv 2\ (\textrm{mod}\ 19) \
\implies 20 \cdot 10^{17} &\equiv 2\ (\textrm{mod}\ 19) \
\implies 10^{17} &\equiv 2\ (\textrm{mod}\ 19) \ \text{\because $20 \equiv 1\ (\textrm{mod}\ 19)$}. \end{align*} $$

Therefore the smallest $n$ for which $10^n=2$ mod $19$ is true is $n=17$. So we have $[(10^{17}−2)/19] \cdot a = 5,263,157,894,736,842 \cdot a = b$.