# What is the smallest number which begins with 7 and if you bring the 7 to the least significant position it becomes a third of the original number?

First I wrote the equation:

$7\times 10^2+c_1\times10^1+c_0\times10^0 = 3(100c_1+10c_0+7)$

which becomes

$679=290c_1+29c_0$

Then I try fix as many variables as possible. In this first iteration, for example, $c_0$ is obviously $1$ because otherwise I would be unable to write the least significant digit of the left hand side of the equation. Then I check if the reminder divides by $29$ and add $630$ to keep things going. Is there a better method?

-

Answer: $$\frac{7241379310344827586206896551}{3} = 2413793103448275862068965517.$$

Solution: Represent your number as $7\cdot 10^k + a$. Then $$7\cdot 10^k+a = 3(10a+7),$$ and $$7\cdot 10^k-29\cdot a-21 = 0.$$ Therefore $29$ divides $7\cdot 10^k - 21 = 7(10^k -3)$. So $29$ divides $10^k -3$. The smallest natural $k$ such that $29$ divides $10^k -3$ is $27$ (see below how we that). From $7\cdot 10^k-29\cdot a-21 = 0$, we get that $a = 241379310344827586206896551$. Then we verify that this is indeed a valid solution.

How can we find the minimum value of $k$ s.t. $\mathbf{10^k \equiv 3 \pmod{29}}$ ? This problem is known as the Discrete Logarithm Problem. It is believed that in general there is no efficient algorithm for it. Since all parameters are very small in this problem, the easiest solution is just to consecutively try $k$ from $1$ to $29$ until we find $k$. In order to compute $10^{k+1} \mathrm{\ mod \ } 29$, we just take $10^{k} \ \mathrm{mod}\ 29$ multiply it by $10$ and divide by $29$. We get, \begin{align*} &{}\ 10^{1} \equiv10, && 10^{2} \equiv 10 \cdot {10} \equiv13, && 10^{3} \equiv 10 \cdot {13} \equiv14, && 10^{4} \equiv 10 \cdot {14} \equiv24,\\ &{}\ 10^{5} \equiv 10 \cdot {24} \equiv8, && 10^{6} \equiv 10 \cdot {8} \equiv22, && 10^{7} \equiv 10 \cdot {22} \equiv17, && 10^{8} \equiv 10 \cdot {17} \equiv25,\\ &{}\ 10^{9} \equiv 10 \cdot {25} \equiv18, && 10^{10} \equiv 10 \cdot {18} \equiv6, && 10^{11} \equiv 10 \cdot {6} \equiv2, && 10^{12} \equiv 10 \cdot {2} \equiv20,\\ &{}\ 10^{13} \equiv 10 \cdot {20} \equiv26, && 10^{14} \equiv 10 \cdot {26} \equiv28, && 10^{15} \equiv 10 \cdot {28} \equiv19, && 10^{16} \equiv 10 \cdot {19} \equiv16,\\ &{}\ 10^{17} \equiv 10 \cdot {16} \equiv15, && 10^{18} \equiv 10 \cdot {15} \equiv5, && 10^{19} \equiv 10 \cdot {5} \equiv21, && 10^{20} \equiv 10 \cdot {21} \equiv7,\\ &{}\ 10^{21} \equiv 10 \cdot {7} \equiv12, && 10^{22} \equiv 10 \cdot {12} \equiv4, && 10^{23} \equiv 10 \cdot {4} \equiv11, && 10^{24} \equiv 10 \cdot {11} \equiv23,\\ &{}\ 10^{25} \equiv 10 \cdot {23} \equiv27, && 10^{26} \equiv 10 \cdot {27} \equiv9, && \boxed{\mathbf{10^{27} \equiv 10 \cdot {9} \equiv3}} \end{align*} (all computations are modulo $29$).

-
You did not say how you found the least $\rm\,k\,$ such that $\rm\:10^k\equiv 3\pmod{\!29}.\:$ Did you employ a computer? For one manual way see my answer. –  Bill Dubuque Dec 5 '12 at 7:03
@BillDubuque, you can use a computer, or compute manually: you need to do just 27 multiplication to find $k$. This problem is known as discrete logarithm and it is widely believed that there is no efficient algorithm for it (an algorithm whose running-time is polynomial in $\log n$), so in general there is no way around that. You can read about it here en.wikipedia.org/wiki/Discrete_logarithm . –  Yury Dec 5 '12 at 15:18
Yes, of course I know that, but the reader may not, so the point of my query was to spur some elaboration for the reader's sake. Remark that one does not need to compute all $27$ values to show, mod $29,$ that $10$ has order $28$. Only a few values suffice, e.g. see the note in my answer. –  Bill Dubuque Dec 5 '12 at 16:51
@BillDubuque, OK, I didn't realize that you were not the OP ;-). In your post you just prove why $10^{27} \equiv 3 \pmod{29}$, you don't give an algorithm that gives you the answer. How is it different from just stating that $10^{27}\equiv 3 \pmod{29}$? Of course, if you know the answer you can find a method that gives it to you quickly. I am still not convinced that there is a better approach than trying all $k$ one-by-one if the modulus is relatively small. –  Yury Dec 5 '12 at 17:23
No, I derived a solution of $\rm\,10^n\equiv 3\ (mod\ 29),\:$ vs. stating a solution. Namely, I noticed that $\,3\,$ is a small negative power of $10,$ so scaling this by $\,\rm 10^{28}\equiv 1\,$ yields $3$ as a positive power of $10,$ $$\rm mod\ 29\!:\,\ 3 \equiv \dfrac{30}{10} \equiv \dfrac{1}{10}\equiv \dfrac{10^{28}}{10}\equiv 10^{27}$$ Then I proved that $\rm\:n = 27\:$ is the minimal $\rm\:n\:$ such that $\rm\:10^n\equiv 3\:$ by proving that $10$ has order $28$, using only a few simple computations mod $29\,$ (vs. computing all $\,26\,$ powers $\,10^2,\, \ldots\,, 10^{27}).$ –  Bill Dubuque Dec 5 '12 at 20:24

Hint $\rm\,\ 7\!\cdot\! 10^n\! +\! a = 3(10a\! +\! 7)\:\Rightarrow\: 29a = 7(10^n\!-\!3)\:$ so $\rm\: mod\ 29\!:\ 10^n\!\equiv 3 \equiv 3/30 \equiv 1/10\equiv 10^{27}$ by little Fermat. By the note below, $\rm\:n=27\:$ is the least solution, so $\rm\:a = 7(10^{27}\!-\!3)/29,\:$ therefore

$$\begin{eqnarray}\rm 7\!\cdot\!10^n\!+\!a &\,=\, & \color{#C00}{21} \dfrac{10^{28}-1}{\color{#C00}{29}} &\,=\,& 7241379310344827586206896551\\ \\ \rm \dfrac{7\!\cdot\!10^n\!+\!a}{3}&= & \ \color{#0A0}{7}\ \dfrac{10^{28}-1}{\color{#0A0}{29}} &=& 2413793103448275862068965517 \end{eqnarray}$$

Exercise $\$ Explain how the above is related to the following periodic decimal expansions

$$\begin{eqnarray} \color{#C00}{21/29} &\,=\, & 0.\overline{7241379310344827586206896551} \\ \color{#0A0}{7/29} &\,=\, & 0.\overline{2413793103448275862068965517} \end{eqnarray}$$

Note $\rm\ n = 27\:$ is the least solution of $\rm\:10^n\equiv 3\pmod{\!29}\:$ since if $\rm\:j<27\:$ and $\rm\:10^j\equiv 3\equiv 10^{27}$ then $\rm\:0\equiv 10^{27}\!-10^j\equiv 10^j(10^{27-j}\!-\!1),\:$ so $\rm\:10\:$ has order $\le 27,\:$ hence one of $\rm\:1,2,4,7,14\:$ by $\rm\:10^{28}\equiv 1;\:$ but that would imply that $\rm\:10^2\equiv \pm1\:$ or $\rm\:10^7\equiv \pm1;\:$ but $\:10^2\equiv 13\not\equiv\pm1,\:$ so $\:10^4\equiv 13^2\equiv -5,\:$ so $\rm\:10^8\equiv 25\not\equiv\pm 10.$

-

Hint: Let $n$ be the number of digits behind the $7$. Then you have $7\cdot 10^n+b=\frac 13 (10b +7)$ for a $b \lt 10$

-