Written by Colin+ in arithmetic, puzzles.

An excellent puzzle I heard from @panlepan (I paraphrase, as I’ve lost the tweet):

When you move the final digit of 142857 to the front, you get 714285, which is five times as large.

What is the smallest positive integer that isdoubledwhen the last digit moves to the front?

There are two approaches I know of: one is dull but effective, the other is a bit more interesting.

Suppose The Number ends with a 1.^{1} Then its double ends with a 2 – so the original number must end with 21.

We can carry on like this – the previous digit must be 4, and the one before that 8.

We now have a number that ends 8421; we’ve reached the “deal with a carry” point of the endeavour. Doubling this gives 16842, so the preceding digit is 6. Doubling 68421 gives 136842, which is where the carry has gone: we would expect doubling the 6 to give us a 2, but the carry from doubling the 8 makes it a 3.

Similarly, we have to deal with the carry from doubling the 6. Doubling the 3 would normally give 6, but because of the carry, gives us 7. Still with me? Our number now ends 7368421.

Proceeding in the same way, the next preceding numbers are 4, 9, 8, 7, 5, 1, 3, 6, 2, 5 and 0, making our number 052,631,578,947,368,421. (The next ones would be 1, 2, 4, taking us back to the start.)

This *does* double if you move the last digit to the front, but starting with a 0 is cheating, don’t you think? However, shifting the 1 at the end to the front gives 105,263,157,894,736,842, which also doubles if you move the last digit to the front – and is the answer to the puzzle.

Suppose our number can be written as $10a + b$, with $a$ and $b$ positive integers such that $1 \le b \le 9$ (and $a$ as big as we like).

The effect of moving $b$ to the front is to make the number $10^k b + a$, where $k = \lceil \log_{10}(a) \rceil$.

That gives us $10^k b + a = 20a + 2b$ (because the effect is also to double the original number).

Rearranging, $(10^k – 2)b = 19a$. For this to be true, $10^k-2$ must be a multiple of 19 (because $b$ certainly isn’t).

But how do we find such a $k$? Enter Fermat.

We know about Fermat’s *Last* Theorem, we’ve had it drilled into us forever. But the Little Theorem? Well, I always need to look it up. It states that, if $p$ is a prime and $a$ a positive integer, then $a^{p-1} \equiv 1 \pmod{p}$.

In particular, $10^{18} \equiv 1 \pmod{19}$.

We also know that $10^{19} \equiv 10 \pmod{19}$, and – because $10\times2 \equiv 1 \mod{19}$, that 10 and 2 are multiplicative inverses.

We know that $10^{36} \equiv 1 \pmod{19}$ (it’s $\br{10^{18}}^2$), and that’s also $\br{10^{17}}\times\br{10^{19}}$ – so $10^{17} \times 10 \equiv 1 \pmod{19}$.

That means $10^{17} \equiv 2 \pmod{19}$ – or alternatively, $10^{17}-2$ is a multiple of 19.

Now all we have to do is divide $10^{17}-2$ by 19 – the Mathematical Ninja would tell you straight away that that’s 52,631,578,947,368,421 – so *that* multiplied by $b$ gives $a$. However, if $b=1$, we hit a problem related to the one before ($k = \lceil \log_{10}(a) \rceil = 16$, rather than 17), so we try $b=2$ instead and get the same number as above.

I’m not saying the second way is *easier*, just a bit more interesting!

- It turns out it doesn’t, but we’ll cross that bridge later. [↩]

## Ernesto La Orden

My own way to remember the Fermat’s Litle Theorem is to write it in this way: a^p = a mod (p).

There is an “a” and a “p” in both sides and they are written in the same order.

## Colin

Nice!