Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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.$

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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