2
$\begingroup$

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$

5 Answers 5

5

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.

3

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

  • 3
    @Nat: This is not precalc, it is arithmetic. You could look under Example at http://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.2012-08-22
3

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.

  • 0
    Ok well in that case shouldn't the OP ask for more detail if needed?2012-08-23
1

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

  • 0
    Yes, that's what Ross hinted at. This works because one is essentially solving a triangular system of equations - see my answer.2012-08-23
1

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

  • 0
    @RijulSaini: that's true, but I was not sure whether the OP was familiar with modular arithmetic, so I showed the modular equivalence explicitly.2012-08-23