2
$\begingroup$

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[0]
    d2 = dParts[1]
    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.

$\endgroup$
2
$\begingroup$

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$$

which is precisely the divisibility test that you discovered. All of the common divisibility tests of this form arise via this general method. Arithmetical inferences like this become very easy once one masters the basics of congruences (or, equivalently, residue or quotient rings), esp. if one masters the fractional viewpoint (equivalently localizations).

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.

$\endgroup$
2
  • $\begingroup$ What sort of classes would i need to take to learn about those topics (congruences, residue or quotient rings, fractional viewpoint, localizations, homogenization). For reference, i have a math minor, where can i go from there? $\endgroup$ – TSA Jan 21 at 15:48
  • $\begingroup$ @TSA Those topics are all covered in courses on abstract and commutative algebra, but applications such as divisibility teste, modular fractions are usually delegated to exercises (If even mentioned). $\endgroup$ – Bill Dubuque Feb 5 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.