Find the smallest positive integer, whose last $4-digit$ part is $2010$ and is divisible by $2011$.

Question

Find the smallest positive integer, whose last $4-digit$ part is $2010$ and is divisible by $2011$.

I solved it in the following way:

I state that $a$ is the number in front of $2010$, in other words if the number we're looking for is $A$, then $A=10^4\cdot a+2010$.

Hence, $a\cdot10^4\equiv1\bmod2011$.

$1956a\equiv1\bmod2011$

$55a\equiv2010\bmod2011$

So $55a=2010+2011k$ for some positive integer $k$.

So $30+31k\equiv 0 \bmod55$

After doing some trial and error for $k\in[0,54]$

$k_{min}=15$

So $55a=32175$, $a=585$.

Hence the smallest number possible is $5850000$

I solved this question using classical number theory and trial-and-error. However, I realize that this question can be solved using the euclidean algorithm. When I looked it up on the internet the only thing I could find was this: https://en.wikipedia.org/wiki/Euclidean_algorithm which is how to find the gcd using euclid's algorithm. Could you please explain to me how to solve the question using the euclidean algorithm, and also please explain to me what the euclidean algorithm is, how it can be applied and some resources to study from?

Answer 1

$\!\bmod \color{#0a0}{2011}\!:\,\ 10^4\! = 5(2000)\equiv 5(-11)\,$ so by simple mental arithmetic

$\ \ \dfrac{1}{10^4}\equiv \dfrac{\color{#c00}1}{-5}\dfrac{1}{11} \equiv \dfrac{\color{#c00}{-2010}}{-5}\dfrac{1}{11}\equiv\dfrac{402}{11}\equiv \dfrac{402+\color{#0a0}{2011\cdot \color{#90f}3}}{11} \equiv\, \bbox[5px,border:1px solid #c00]{585}$

We used inverse reciprocity $\bmod 11\!:\ 0\equiv 402+\color{#0a0}{2011\cdot \color{#90f}k}\equiv 6\!-\!2k\!\iff\! \color{#90f}{k\equiv 3}\,$ makes exact the quotient by $11,\,$ and we cast out $11$'s, e.g. $\bmod 11:\ 2011\equiv -2\!+\!0\!-1\!+\!1\equiv-2$.

Answer 2

We have $$30+31k \equiv 0 \pmod{55}$$

$$31k \equiv -30 \equiv 25 \pmod{55}$$

Let us find $31^{-1}\pmod{55}$

\begin{align} 55 &= 31 + 24\\ 31 &= 24 + 7 \\ 24 &= 3(7)+3 \\ 7 &= 2(3)+1 \end{align}

Hence we can write \begin{align} 1 &= 7 - 2(3)\\ &= 7 - 2(24-3(7))\\ &=7(7)-2(24) \\ &= 7(31-24) - 2(24)\\ &= 7(31)-9(24)\\ &= 7(31) - 9(55-31)\\ &= 16(31) - 9(55) \end{align}

Hence we can conclude that $31^{-1} \equiv 16 \pmod{55}$.

From $31k \equiv 25 \pmod{55}$, we have

$$k \equiv 31^{-1}(25) \equiv 16(25) \equiv 400 \equiv 15\pmod{55} $$

which agrees with your solution. They key is to learn to find the modulo inverse.

Answer 3

Update: just found another way. Not the simplest but very safe and calculator-free because dividing by 10 is easy.

$$ \pmod{2011}: \frac{1}{10^4} \equiv \frac{-2010}{10^4} \equiv \frac{-201+2011}{10^3} \equiv \frac{181-2011}{100} \equiv \frac{-183+2011\cdot 3}{10} = 585. $$

---

I recently learned Gauss's Algorithm from Bill Dubuque (How to find the inverse modulo m?). Let's try:

$$ \frac{1}{10^4}\equiv \frac{1}{-55} \equiv \frac{36}{-55\cdot 36} \equiv \frac{36}{31} \equiv \frac{36\cdot 65}{31\cdot 65} \equiv \frac{329}{4} \equiv \frac{329+2011}{4}=\frac{2340}{4} =585 \pmod{2011}.\blacksquare $$

Or, even simpler $$ \frac{1}{10^4}\equiv \frac{-2010}{-55} = \frac{402}{11} \equiv \frac{402\cdot 183}{11\cdot 183} \equiv \frac{1170}{2} = 585 \pmod{2011}. $$

Answer 4

Euclidean Algorithm

$A= 10000K + 2010 = 2011M$ so

$10000K = 2011M -2010 = 2011M-2011 +1 = 2011(M-1) = 1$

$10000K -2011(M-1) = 1$.

Find a small solution to $K, M-1$.

$10000 = 4*2011 + 1956;$ $1956=10000 - 4*2011$

$2011=1956 + 55;$ $55= 2011-1956 = 2011-(10000 -4*2011)=5*2011-10000$.

$1956 = 35*55 + 31;$ $31=1956-35*55= (10000-4*2011)- 35(5*2011-10000)= 36*10000-179*2011$

$55 = 31 + 24;$ $24 = 55-31 = (5*2011-10000)- (36*10000-179*2011)=-37*10000+184*2011$

$31 = 24 + 7;$ $7 =31 -24 =(36*10000-179*2011) - (-37*10000+184*2011)=73*10000 -363*2011$

$24 = 3*7 + 3;$ $3=24-3*7=(-37*10000+184*2011)-3(73*10000 -363*2011)=-256*10000+1273*2011$

$7 = 2*3 + 1$ $1= 7-2*3 = (73*10000 -363*2011)- 2(-256*10000+1273*2011)=585*10000-2909*2011$

So if we let $K=585$ and $M-1=2909$ we get $5852010 = 2011*2910$