1
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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$?) $\endgroup$ Jul 5, 2023 at 12:00
  • $\begingroup$ Thanks, that's clear. So would my approach work in general (solve using irreversible identities, then check for extraneous solutions by substituting back into the original equation)? $\endgroup$ Jul 5, 2023 at 12:27
  • 1
    $\begingroup$ @user11350388 I would suggest looking at this : wrean.ca/cazelais/linear_congruence.pdf $\endgroup$
    – Sathvik
    Jul 5, 2023 at 13:00
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .