# Find the smallest positive multiple of $1999$ that ends in $2006$ (last four digits)

Find the smallest positive multiple of $$1999$$ that ends in $$2006$$ (last four digits)

Approach:

$$1999N\equiv 2006\pmod{10000}$$

(1) $$9995N\equiv-5N\equiv30\pmod{10000}$$

(2) $$-N\equiv 6 \pmod{2000}$$, so $$N\equiv 1994\pmod{2000}$$.

(3) At this point, we still need to plug this back into the original congruence, giving:

$$1999(2000K-6)\equiv2006\pmod{10000}$$

$$1999\cdot2000K\equiv2006+6\cdot1999 \pmod{10000}$$

$$8000K\equiv2006+1994\equiv 4000\pmod{10000}$$, so finally,

$$4K\equiv2\equiv12\pmod{5}$$ and $$K\equiv3\pmod{5}$$, meaning that $$N=2000\cdot3-6=\boxed{5994}$$ (testing verifies this).

I was wondering, why are there 'extraneous solutions' to $$N\equiv 1994\pmod{2000}$$, which results in the need for substituting back into the equation (step 3)? Is it because the division between step (1) and (2)? I don't think so, because that step should be reversible.

$$1999N\equiv 2006\pmod{10000}\implies 9995N\equiv 30\pmod{10000}~$$, but the statement $$~9995N\equiv 30\pmod{10000}\implies 1999N\equiv 2006\pmod{10000}$$ is incorrect.
• For example, $5\times 2000\equiv 5\times 4000\equiv 0\pmod{10000}$, so the step isn't reversible. If, however, your congruence had been of the form $ax\equiv b \pmod{n}$ where $a$ and $n$ were coprime, the step would be reversible. The issue is about the existence and uniqueness of a multiplicative inverse (in other words, can we divide by $a$?) Jul 5, 2023 at 12:00
As said by @Sathvik, the first step is not reversible but you have the right answer. This is due to the fact that $$5$$ and $$10000$$ are not coprime, hence $$5$$ is not invertible in the ring $$\mathbb{Z}/10000\mathbb{Z}$$. However, $$1999$$ is, because it is not divisible by $$2$$ neither by $$5$$.
Therefore, it admits an inverse and $$1999N \equiv 2006\ [10000]$$ is equivalent to $$N \equiv 1999^{-1} \cdot 2006\ [10000]$$. Now, we have to find $$1999^{-1}$$. In other words, we want to find an integer $$k$$ such that $$1999k \equiv 1\ [10000]$$. For this, apply Bézout algorithm, \begin{align*} 10000 & = 1999 \cdot 5 + 5 \textrm{ (1)}\\ 1999 & = 5 \cdot 399 + 4 \textrm{ (2)}\\ 5 & = 4 \cdot 1 + 1 \textrm{ (3)}\\ 5 & = (1999 - 5 \cdot 399) \cdot 1 + 1 \textrm{ by (2) and (3),}\\ 5 \cdot 400 & = 1999 \cdot 1 + 1\\ (10000 - 1999 \cdot 5) \cdot 400 & = 1999 \cdot 1 + 1 \textrm{ by (1),}\\ 10000 \cdot 400 & = 1999 \cdot 2001 + 1. \end{align*} We deduce that in $$\mathbb{Z}/10000\mathbb{Z}$$, we have $$1999^{-1} = -2001 = 7999$$ hence $$N = 7999 \cdot 2006 = 16045994 = 5994$$. $$0 \leqslant 5994 < 10000$$ is the smallest non negative integer that represents its class modulo $$10000$$ hence the smallest $$N$$ is indeed $$5994$$.