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?
Best Answer
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)$