How is moving the last digit of a number to the front and multiplying related to multiplicative orders?

There seems to be a relationship between multiplicative orders modulo $n$ and a puzzle Presh Talwalkar gave a few days ago at https://www.youtube.com/watch?v=1lHDCAIsyb8

I'm hoping someone can give a more rigorous explanation of the pattern I see.

$\bullet\textbf{ The Puzzle }\bullet$

He states the puzzle as: "What Positive Number Doubles When Its Last Digit Becomes Its First Digit?"

For example, the smallest solution - assuming base-10 representation - is $105263157894736842$. Which means that $$(2)\cdot105263157894736842 \quad\ \ \ $$ $$||$$ $$210526315789473684$$

Naturally, one can proceede to find solutions in other bases. The base-5 solution is $$(2)\cdot102342_5 \quad\ \ \ $$ $$||$$ $$210234_5$$

$\bullet\textbf{ Multiplicative Order Connection }\bullet$

The base-10 solutions is $18$ digits and the base-5 solution is $6$ digits. I wrote a program to generate the smallest solution in all bases and then counted the number of digits in each such solution. Here's the sequence, starting with base-2 $$2,4,3,6,10,12,4,8,18,6,11,20,...$$ $$\uparrow \quad\quad\quad\quad\ \uparrow \quad\quad$$ $$\text{Base-} 5 \quad\quad\quad \text{Base-} 10 \quad\quad$$ A quick search on http://oeis.org/ shows that these numbers are the multiplicative order of $$2\ (\text{mod } 2B-1)$$ where $B$ is the representation base we are working in. See http://oeis.org/A002326

This puzzle can be further generalized by finding numbers that triple instead of double upon moving the last digit to the front. Let's introduce an arbitrary multiplying factor: $k$

So the solutions mentioned above and Talwalkar's puzzle are a particular case when $k=2$

For a different example, let's look at $k=5$ in base-7. The smallest solution is $$(5) \cdot 1013042156536245_7 \quad\ \ \ $$ $$||$$ $$5101304215653624_7$$

This solution is $16$ digits long. As we did before for base-10, we can write out a sequence of the number of digits in each base's solution starting with base-2 $$6,6,9,2,14,16,4,5,42,18,...$$ $$\uparrow\ \ $$ $$\text{Base-}7\ \ $$ Another search on http://oeis.org/ quickly shows that these numbers are the multiplicative order of $$5\ (\text{mod } 5\cdot7-1)\quad\text{or rather}\quad 5 \ (\text{mod }34)$$

$\bullet\textbf{ A Conjecture }\bullet$

The pattern might be clear now. After checking other cases, it seems that the smallest positive number in any base $B$ - which is $k$ times the value gotten by moving it's last digit to the front - has a number of digits equal to the multiplicative order of $$k\ (\text{mod } Bk-1)$$ I can see how multiplicative order would be related to this problem. But I can't find an exact reason why this relationship should be so. Is there an intuitive reason?

Solution 1:

Given some solution in base $B$ - let's start by assigning the variable $x$ to the digit that get's moved to the front and assigning to the variable $y$ to the rest of the number (Talwalkar did this in his video). So if we have a multiplying factor of $k$ we are looking for a solution to $$k(By+x)=B^nx+y$$ $$\text{where}\quad 0<x<B \quad\text{and}\quad n > \text{log}_B(y) \quad\text{and}\quad B\geq2 \quad\text{and}\quad 2\leq k < B$$ rearranging we get $$y = \frac{x(B^n-k)}{Bk-1}$$ Since $y$ is an integer we conclude that either $x$ or $B^n-k$ is divisible by $Bk-1$. But $x$ can't be divisible by $Bk-1$ because we have $$x<B<2B-1\leq Bk-1\quad\Rightarrow\quad x<Bk-1$$ Therefore $B^n-k$ must be divisible by $Bk-1$. Accordingly we write $$B^n-k\equiv 0\ (\text{mod }Bk-1)$$ $$\Updownarrow$$ $$ \quad\quad\quad\quad\quad\quad k\equiv B^n\ (\text{mod }Bk-1) \quad\quad\quad\quad\quad(1) $$ We are almost there. Next we need to note a simple property of our modular arithmetic, namely that $Bk$ has a remainder of $1$ when divided by $Bk-1$ (duh). So we say that $$Bk\equiv 1\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$ \quad\quad\quad\quad\quad\quad (Bk)^n\equiv 1\ (\text{mod }Bk-1) \quad\quad\quad\quad\quad(2) $$ Now we multiply the left and right sides of equations $(1)$ and $(2)$ respectively and observe $$k\cdot(Bk)^n\equiv B^n\cdot1\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k^{n+1}B^n\equiv B^n\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k^{n+1}\equiv 1\ (\text{mod }Bk-1)$$ Which means that $n+1$ is the multiplicative order of $k\ (\text{mod }Bk-1)$. But before we conclude that the solution also has $n+1$ digits, more needs to be said.

The smallest solution has $1$ as it's first digit. Since $x$ is the first digit of the solution times $k$, we can conclude that $x=k$. Now to put it all together, our solution is $$By+x=\frac{1}{k}(B^nx+y)=\frac{1}{k}(B^nk+y)=B^n+\frac{y}{k}$$ which has $n+1$ digits.

$\bullet\textbf{ Conclusion }\bullet$

We saw that the multiplicative order of $k\ (\text{mod }Bk-1)$ is the number of digits in the smallest solution to Talwalkar's puzzle for the base $B$ and multiplying factor $k$.

It should be noted that we can also conclude that $k$ and $B$ have the same multiplicative order here. As follows $$k\cdot1\equiv B^n\cdot(Bk)\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k\equiv B^{n+1}k\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$1\equiv B^{n+1}\ (\text{mod }Bk-1)$$

The smallest solution has the same number of digits as the multiplicative order of $B\ (\text{mod }Bk-1)$ and of $k\ (\text{mod }Bk-1)$