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!
[Math] Divisibility Rules of 2019
divisibility
Related Solutions
Claim 1:
The divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n+1$'. Let '$s$' denote the sum of digits of '$a$' expressed in base '$n+1$'. Now $n|a \iff n|s$. More generally, $a \equiv s \pmod{n}$.
Example:
Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $14$. $$611 = 3 \times 14^2 + 1 \times 14^1 + 9 \times 14^0 = (319)_{14}$$ where $(319)_{14}$ denotes that the decimal number $611$ expressed in base $14$. The sum of the digits $s = 3 + 1 + 9 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.
Proof:
The proof for this claim writes itself out. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n+1$'. $$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$$ Now, note that \begin{align} n+1 & \equiv 1 \pmod n\\ (n+1)^k & \equiv 1 \pmod n \\ a_k \times (n+1)^k & \equiv a_k \pmod n \end{align} \begin{align} a & = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0 \\ & \equiv (a_m + a_{m-1} \cdots + a_0) \pmod n\\ a & \equiv s \pmod n \end{align} Hence proved.
Claim 2: The divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n-1$'. Let '$s$' denote the alternating sum of digits of '$a$' expressed in base '$n-1$' i.e. if $a = (a_ma_{m-1} \ldots a_0)_{n-1}$, $s = a_0 - a_1 + a_2 - \cdots + (-1)^{m-1}a_{m-1} + (-1)^m a_m$. Now $n|a$ if and only $n|s$. More generally, $a \equiv s \pmod{n}$.
Example:
Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $12$. $$611 = 4 \times 12^2 + 2 \times 12^1 + B \times 12^0 = (42B)_{12}$$ where $(42B)_{14}$ denotes that the decimal number $611$ expressed in base $12$, $A$ stands for the tenth digit and $B$ stands for the eleventh digit. The alternating sum of the digits $s = B_{12} - 2 + 4 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.
Proof:
The proof for this claim writes itself out just like the one above. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n-1$'. $$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$$ Now, note that \begin{align} n-1 & \equiv (-1) \pmod n\\ (n-1)^k & \equiv (-1)^k \pmod n \\ a_k \times (n-1)^k & \equiv (-1)^k a_k \pmod n \end{align} \begin{align} a & = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0 \\ & \equiv ((-1)^m a_m + (-1)^{m-1} a_{m-1} \cdots + a_0) \pmod n\\ a & \equiv s \pmod n \end{align} Hence proved.
Pros and Cons:
The one obvious advantage of the above divisibility rules is that it is a generalized divisibility rule that can be applied for any '$n$'.
However, the major disadvantage in these divisibility rules is that if a number is given in decimal system we need to first express the number in a different base. Expressing it in base $n-1$ or $n+1$ may turn out to be more expensive. (We might as well try direct division by $n$ instead of this procedure!). However, if the number given is already expressed in base $n+1$ or $n-1$, then checking for divisibility becomes a trivial issue.
One rule I use pretty much is:
If you double the last digit and subtract it from the rest of the number and the answer is: 0, or divisible by 7 then the number itself is divisible by 7.
Example:
- 672 (Double 2 is 4, 67-4=63, and 63÷7=9) Yes
- 905 (Double 5 is 10, 90-10=80, and 80÷7=11 3/7) No
If the number is too big you can repeat until you find the solution.
Best Answer
$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.