Divisibility of big numbers

Suppose we have a number $N$ with $x$ digits and we want to determine whether $N$ is divisible by a number $M$ with $y$ digits such that $x > y$.

How do I go about this? I tried to use the first $y$ digits of $N$ and divide them by $M$ but I'm not sure this is true for all $N$ and $M$. Is there a general rule of thumb for problems like this?

Answer

The method below is good for small values $y$. Say, for $y\le 12$.

And it is closely related to divisibility rules.

Explained via example:


let

$$N = 1529773658514887677106240187604962388655195023566;$$
$$M=14159.$$

Since $y=5$, we group digits of the number $N$ by $5$:
$$N = \color{gray}{0}1529\;\;77365\;\;85148\;\;87677\;\;10624\;\;01876\;\;04962\;\;38865\;\;51950\;\;23566;\tag{1}$$
and rewrite $N$ as
$$N = a_9\cdot 100000^9 + a_8 \cdot 100000^8 + \cdots + a_1 \cdot 100000 + a_0,\tag{2}$$
where $0\le a_j < 100000$.

We'll find number $v$ ($0\le v < 100000$), for which
$$N \equiv v (\bmod M).\tag{3}$$
If $v=0$, then $N$ is divisible by $M$.

So, we find remainders of $10000$, $10000^2$, $\ldots$, $10000^9$ first:
\begin{array}{rcr}
100000 &\equiv &\color{darkred}{887} (\bmod 14159),\\
100000^2\equiv 887\cdot 887=786769 &\equiv &\color{darkred}{8024} (\bmod 14159),\\
100000^3\equiv 887\cdot 8024=7117288 & \equiv &\color{darkred}{9470} (\bmod 14159),\\

& \cdots & \\
100000^8 &\equiv &\color{darkred}{11965} (\bmod 14159),\\
100000^9 &\equiv &\color{darkred}{7864} (\bmod 14159).
\end{array}

Therefore
\begin{array}{r}N \equiv 01529\cdot \color{darkred}{7864} \\
+ 77365 \cdot \color{darkred}{11965} \\
+ \cdots \quad\\
+ 04962 \cdot \color{darkred}{9470} \\

+ 38865 \cdot \color{darkred}{8024} \\
+ 51950 \cdot \color{darkred}{887} \\
+ 23566 \cdot \color{darkred}{1} \\
\equiv 0 (\bmod 14159).
\end{array}
So, $N$ is divisible by $M$.

---

Relation to divisibility rules:


if $M=3$, then $y=1$, and we note that
$$10\equiv 1 (\bmod 3);\\
10^2\equiv 1 (\bmod 3);\\
10^3\equiv 1 (\bmod 3);\\
\cdots$$
and for $$N=a_j\cdot 10^j + a_{j-1}\cdot 10^{j-1}+\cdots + a_1\cdot 10 + a_0$$
we have
$$N\equiv a_j + a_{j-1}+\cdots + a_1 + a_0 (\bmod 3)$$
(iif $N$ is divisible by $3$ then sum of its digits is divisible by $3$).