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
    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.2012-12-05
  • 0
    @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 http://en.wikipedia.org/wiki/Discrete_logarithm .2012-12-05
  • 0
    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.2012-12-05
  • 0
    @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.2012-12-05
  • 0
    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}).$2012-12-05
  • 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