# Proof of general divisibility rule

I am looking for proof of, or a suggestion on how to start on a proof of, or any general insights into, the following statement:

$$n\equiv0~~(\text{mod}~d) \implies f(n,d,s)\equiv0~~(\text{mod}~d)$$

$$f$$ is the following:

• Separate both $$n$$ and $$d$$ into groups of digits of size $$s$$, starting from the right
• $$s$$ must be assigned so that $$d$$ is split into two groups
• $$n$$ will now be split into at least 2 groups and $$d$$ will be split into exactly 2 groups, $$d_1$$ and $$d_2$$ which are, respectively, the left and right parts of $$d$$
• Multiply each $$n$$ group by $$d_1^l$$ where $$l$$ is the groups distance from the leftmost $$n$$ group
• Multiply each $$n$$ group by $$d_2^r$$ where $$r$$ is the groups distance from the rightmost $$n$$ group
• Take the absolute value of the alternating sum of the new $$n$$ groups

An example:

• Start with $$n = 39445434288 = 2843529 * 13872$$, $$d = 13872, s = 4$$
• Separate $$n$$ into $$n_1=394,n_2=4543,n_3=4288$$
• Separate $$d$$ into $$d_1 = 1$$, $$d_2 = 3872$$
• Now $$f(n,d,s) = |(n_1*d_1^0*d_2^2) - (n_2*d_1^1*d_2^1) + (n_3*d_1^2*d_2^0)|$$
• $$f(n,d,s) = |394*1*64269752490-4543*1*3872+4288*1*1|$$
• $$f(n,d,s) = |5889413088| = 5889413088 = 424554 * 13872$$

Repeating this on the subsequent values of $$f(n,d,s)$$ yields a sequence that decreases to zero:

39445434288, 5889413088, 834941808, 106412112, 12512544, 4841328, 1872720, 721344, 277440, 97104, 27744, 0


Every number in the sequence is divisible by $$d = 13872$$

This function doesn't, however, have the property $$n\equiv f(n,d,s)~~(\text{mod}~d)$$ as the remainder will change if $$n$$ is not divisible by $$d$$:

Below is some ugly python code for the function that I made (I lost the original from months ago):

def getParts(num:int, n:int) -> list:
s = str(num)
l = []
while len(s) % n != 0:
s = "0" + s
for i in range(0, len(s), n):
l.append(int(s[i:(i+n)]))
return l

def testFunc(n:int, d:int, size:int=-1) -> int:
if n < d:
return n
if size == -1:
size = int(round(len(str(d)) / 2))
nParts = getParts(n, size)
dParts = getParts(d, size)
d1 = dParts
d2 = dParts
for i in range(len(nParts)):
nParts[i] *= d1 ** i
for i in range(len(nParts)):
nParts[len(nParts) - i - 1] *= (d2 ** i) * (-1) ** i
return abs(sum(nParts))


A sequence of numerators from the function does not always reach 0. Sometimes it oscillates between a few values forever.

I am, however, fairly certain that a sequence of numerators from the function will never diverge to infinity.

If needed, I can post data on how the function performs with different $$s$$, as well as detailed data on how many iterations of the function it requires to reach 0 (when $$n$$ is a multiple of $$d$$)

This function is extremely interesting to me and I would greatly appreciate any insights into it.

This equivalence arises by working in radix $$\,t = 10^4\,$$ so $$\bmod d = d_1 t + d_0\,$$ we have $$\,t \equiv -d_2/d_1\,$$ is congruent to a  fraction,  so $$\, 0\equiv n = n_1 t^k + \cdots + n_{k+1} t^0 =: f(t)$$ $$\iff\! 0\equiv d_1^k f(t),\,$$ where scaling by $$\,d_1^k\,$$ clears the denominators after evaluating $$\,f(t)\,$$ at $$\,t\equiv -d_2/d_1\,$$ (which uniquely exists $$\bmod d\iff d_1^{-1}$$ uniquely exists $$\!\bmod d$$ $$\!\iff\! \color{#0a0}1 = (d_1,d) = (d_1,d_1 t+d_2) = \color{#0a0}{(d_1,d_2)},\,$$ i.e. $$\!\iff\!$$ the radix $$\,t\,$$ digits $$\,d_i$$ are $$\rm\color{#0a0}{coprime}),\,$$ e.g. for your $$\,n\,$$ with $$\,3\,$$ digits $$\,(k = 2)\,$$ we have
\begin{align} \bmod\, d \:\!=\:\! d_1 \:\! t + d_2\!: &\ \ \ \,\color{#0a0}{d_1\:\! t}\equiv \color{#c00}{-d_2}\\[.2em] {\rm thus}\ \ \, 0 \equiv\ &\!n\! =\! n_1\, t^2\, +\, n_2\, t \,+\, n_3\\[.2em] \iff 0\equiv\ &d_1^2 \,(n_1\, t^2 \,+\, n_2\, t \,+\, n_3),\, \ {\rm by}\ \ (d_1,d) = 1\\[.2em] \equiv\ & n_1 (\color{#0a0}{d_1 t})^2 \,+ n_2 d_1 (\color{#0a0}{d_1 t})\ \,+ d_1^2\, n_3\\[.2em] \equiv\ & n_1 (\color{#c00}{-d_2})^2\! + n_2 d_1 (\color{#c00}{-d_2}) + d_1^2\, n_3\\[.2em] \equiv\ & n_1\, d_1^0\,d_2^2\ -\ n_2\, d_1^1\, d_2^1\ +\ d_1^2\, d_2^0\, n_3 \end{align}\qquad\qquad
Remark $$\ d_1^k f(d_2/d_1)$$ is a homogenization of $$\,f(t).\,$$ For geometric intuition behind such see e.g. the answers to this question.