# $1867k =\ldots 1992$, $k\in\mathbb{Z}^+$. Find the minimum value of k.

The number $1867$ is multiplied by a positive integer $k$. The last four digits of the product are $1992$. Determine the minimum value of $k$.

$1867k =\ldots 1992$

-

Hint $\$ Let $\rm\, k = \ldots\!dcba$ have undetermined digits. Multiplying and comparing digits yields

$$\rm\begin{eqnarray} 1867\,(\ldots\!dcba)\ &= &\rm\ (7+6\cdot10+8\cdot 10^2 + 10^3)\,(a + b\cdot 10 + c\cdot 10^2+ d\cdot 10^3 + (\cdots)\, 10^4)\\ & =&\rm\ 7a + (6a\!+\!7b)\, 10 + (8a\!+\!6b\!+\!7c)\, 10^2 + (a\!+\!8b\!+\!6c\!+\!7d)\,10^3+ (\cdots)\, 10^4\\ & =&\rm\, \ldots\!1992\end{eqnarray}$$

$10^0$ digit: $\rm\ mod\ 10\!:\ 2\equiv 7a\:\Rightarrow\: a\equiv 6,\:$ so $\rm\:7a = 42,\:$ with carry $\color{#C00}4$

$10^1$ digit: $\rm\ mod\ 10\!:\ 9\equiv 6\cdot6 + 7b+\color{#C00}4\equiv 7b\:\Rightarrow\:b\equiv 7,\,$ so sum $= 89,$ with carry $= \color{#0A0}8$

$10^2$ digit: $\rm\ mod\ 10\!:\ 9 \equiv 8\cdot6\!+\!6\cdot 7\!+\!7c\!+\!\color{#0A0}8 \equiv 7c\!+\!8\,\Rightarrow\,7c\equiv 1\,\Rightarrow\,c\equiv 3,\,$ sum $=119,\,$ carry $=\color{brown}{11}$

$10^3$ digit: $\rm\ mod\ 10\!:\ 1 \equiv 6 + 8\cdot 7 + 6\cdot 3+ 7d + \color{brown}{11}\equiv 7d +1\,\Rightarrow\, 7d\equiv 0\,\Rightarrow\,d\equiv 0$

Therefore $\rm\:a + b\cdot 10 + c\cdot 10^2+ d\cdot 10^3 = 376.\:$ Indeed $\rm\:1867\cdot 376 = 701992.$

Remark $\$ As Ross hinted, one may solve it iteratively, examing it mod $10, 10^2, 10^3, 10^4.\:$ This works because the above system of modular equations has nice triangular form: with carries $\rm\:c_i$

$$\rm \left[\begin{array}{cccc} 7 & 6 & 8 & 1 \\ 0 & 7 & 6 & 8 \\ 0 & 0 & 7 & 6 \\ 0 & 0 & 0 & 7 \end{array}\right]\left[\begin{array}{c} d\\ \rm c\\ \rm b\\ \rm a\end{array}\right] + \left[\begin{array}{c}\rm c_3 \\\rm c_2\\ \rm c_1\\ 0\end{array}\right] \equiv \left[\begin{array}{c} 1\\9\\9\\2\end{array}\right]$$

The point of writing it out in this slight longer form is to explicitly exhibit this special structure - so to make clear the reason it works. This is perhaps better known in the analogous power series case, e.g. for computing inverses, Newton iteration, etc.

-

Hint: you can find the digits of $k$ from the right. 7 times what ends in 2?

-
7 x 6 = 42, does that mean the first digit is 6? Where do I go from there? – Nat Aug 22 '12 at 22:27
@Nat: Yes. Now think about the tens digit. What does it have to be to make the tens digit of the product be 9? Remember the carry of 4. – Ross Millikan Aug 22 '12 at 22:45
@Nat - Well, where would you have to go from there? Think. – user5137 Aug 22 '12 at 22:45
@Nat: If you make the diagram of a standard long multiply problem, with an unknown number of blanks for the digits of $k$ times 1867, and blanks for the partial products, you are given the right four digits of the final product. So you can fill in the things you know to get the things you don't. – Ross Millikan Aug 22 '12 at 22:48
@Nat: This is not precalc, it is arithmetic. You could look under Example at en.wikipedia.org/wiki/Long_multiplication#Long_multiplication The partial products are the lines 00000000, 71874699, 191665864, 119791165 which represent one digit of the multiplier times the multiplicand. – Ross Millikan Aug 22 '12 at 23:54

If you want to crack a nut with a sledgehammer then write this equation as:

$1867x - 10000y = 1992$

for positive integers $x,y$. Then we are left with a Diophantine equation. Solve this in the usual fashion and rejig the numbers to find the "smallest" solution for $x$ such that $y$ is positive.

-
My impression is that OP most likely is not yet advanced far enough to about the usual way of solving linear Diophantine equations. – Marc van Leeuwen Aug 23 '12 at 3:13
I wrote little because last time I provided a full solution to a question I was told I wasn't leaving the OP anything to do! – fretty Aug 23 '12 at 9:49
Leaving something for OP to do can be a good idea, especially when one feels that it is easy and actually doing it is more instructive than being told everything. But part of the game of answering questions is also guessing from the way the question is formulated what OP does already know, and at what level she is capable of understanding an answer. That is what my comment was hinting at (and I forgot the type the crucial word "know", as you my have guessed; sorry about that). – Marc van Leeuwen Aug 23 '12 at 11:44
Ok well in that case shouldn't the OP ask for more detail if needed? – fretty Aug 23 '12 at 13:27
Definitely..... – Marc van Leeuwen Aug 23 '12 at 15:30

Tune the digits one by one.

Step 1: $186[7] \to 199[2]$. Multiply $1867$ by $6$ gives the correct last digit [2].
Now you have $1867\times6=\cdots120[2]$.

Step 2: $12[02] \to 19[92]$. The tens digit should $+9$. Recall that $7\times7=\cdots9$.
Now you have $1867\times76=\cdots18[92$].

Step 3: $1[892] \to 1[992]$. The hundreds digit sould $+1$. $7\times3=\cdots1$.
So, $1892\times\color{green}{376}=\cdots[1992]$.

-
Yes, that's what Ross hinted at. This works because one is essentially solving a triangular system of equations - see my answer. – Bill Dubuque Aug 23 '12 at 2:51

Using the Euclid-Wallis Algorithm to solve the equation $$10000m+1867k=1992$$ Since the $(1867,10000)=1$ we can find a linear combination of $1867$ and $10000$ that equals $1$. $$\begin{array}{r} &&5&2&1&4&5&8&3\\\hline 1&0&1&-2&3&-14&73&-598&1867\\ 0&1&-5&11&-16&75&-391&3203&-10000\\ 10000&1867&665&537&128&25&3&1&0\\ &&&&&&&{\uparrow}&{\star} \end{array}$$ From the column with the arrow, we get that $$10000(-598)+1867(3203)=1\tag{1}$$ Multiply $(1)$ by $1992$ to get $$10000(-1191216)+1867(6380376)=1992\tag{2}$$ Add $638$ times $10000(1867)+1867(-10000)=0$ (from the colum with the star) $$10000(1191146)+1867(-6380000)=0\tag{3}$$ to get $$10000(-70)+1867(376)=1992\tag{4}$$ Thus, the minimum positive such $k$ is $376$.

-
From $(2)$, you could take $\pmod{10000}$ directly to get $6380376 \equiv \boxed{376} \pmod {10000}$ as the answer. – Rijul Saini Aug 23 '12 at 10:19
@RijulSaini: that's true, but I was not sure whether the OP was familiar with modular arithmetic, so I showed the modular equivalence explicitly. – robjohn Aug 23 '12 at 16:20