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.
Best Answer
The first step is not 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.