3
$\begingroup$

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?

3 Answers 3

0

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$

7

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

4

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

  • 0
    While the above is not a general method to compute discrete logs, it is a handy optimization for manual calculations - one that frequently proves applicable to small problems due to the *law of small numbers*. Since you originally gave no clue whatsoever as to how you obtained your solution, I wondered if perhaps you employed some other handy technique, hence my initial comment.2012-12-05