Divisibility Rules of 2019

Question

What is the divisibility rule or way to find that a number is divisible by 2019 and we can't divide the number by 2019 to test it? and how do we prove that the rule works for 2019?

Help is appreciated!

Answer 1

$2019 = 3(673)\,$ so it suffices by CRT to compute the remainders mod $3\,$ & $\,673$.

$\!\!\bmod 3\!:\,$ the remainder is congruent to the digit sum (as in casting out nines).

$\!\!\bmod 673\!:\ 10^{\large 14}\equiv 8\,$ so we can use that to work in chunks of $\,14\,$ decimal digits, e.g.

$\ n = 8100000000000025= 81(10^{\large 14})+25 \equiv 81(8)+25\equiv 673\equiv \color{#0a0}0$

$ $ By $ $ Easy $ $ CRT: $\,\ \ \ \begin{align} &n\equiv \color{#0a0}a\pmod{\!673}\\ &n\equiv\color{#c00} b\pmod{\!3}\end{align}\iff\, n\equiv \color{#0a0}a + 673(\color{#c00}b\!-\!\color{#0a0}a)\,\pmod{\!2019}$

e.g. above $\,n\equiv 8\!+\!1+\!2\!+\!5\equiv\color{#c00} 1\pmod{\!3}\,$ so $\ n\equiv \underbrace{\color{#0a0}0+673(\color{#c00}1\!-\!\color{#0a0}0)}_{\large 673}\,\pmod{\!2019}$

For some numbers this may be faster than the universal divsiibility test, which is essentially a modular form of the long division algorithm that ignores the quotients.

Answer 2

In the spirit of the usual rule for $7$, which checks whether a number is divisible but does not give the remainder if not, given a number $n$ to check, you can delete the last digit of $n$ and add $202$ times that digit to the result. You can keep going until you get down to four digits and there are not many multiples of $2019$ with four digits.

It works because if the last digit is $d$ we are saying that $n$ is divisible by $2019$ if and only if $n+2109d$ is, but $n+2019d$ ends in $10$ so we can divide by $10$.

As an example, if $n=954987$ we next get $$95498+202\cdot 7=96912\\ 9691+202\cdot 2=10095\\ 1009+5\cdot 202=2019$$ so $954987$ is divisible by $2019.$ In fact it is $2019 \cdot 473$