11
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.