What is the proof of divisibility by $13$? [duplicate]

While solving the question of $26^{th}$ digit given by @The Lone Wolf a question arrived in my mind; the question was

Everyone knows the divisibility rule of $13$.

Test for divisibility by $13$: Add four times the last digit to the remaining leading truncated number. If the result is divisible by 13, then so was the first number.

For Example : $$50661$$ $$5066+4=5070$$ $$507+0=507$$ $$50+28=78$$

and $78$ is $6\times13$, so $50661$ is divisible by $13.$

Please help me!!!

Hint $\ 13\mid 10a\!+\!b\iff 13\mid \color{#c00}4\,(10a\!+\!b)\equiv \bbox[5px,border:2px solid red]{a\!+\!4b}\pmod{\!13}$

i.e. $ $ scale $\ 10a\!+\!b\,\ $ by $\, \dfrac{1}{10}\equiv \dfrac{-12}{-3}\equiv \color{#c00}4\,\pmod{\!13}\ $ to make $a$'s coef $\equiv 1.$

Remark $ $ This works for any modulus $\,n\,$ coprime to the radix $\,r\, $ (by $1/r$ exists mod $n$ by Bezout).

However, the universal divisibility test given here is often simpler, and has the major advantage of computing true remainders, so it can be used for general arithmetic mod $n$

First, let me prove a more general statement: if $P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$, a polynomial with integer coefficients, is divisible by $x+3$, then $Q(x)=a_nx^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2x+a_1+4a_0$, when divided by $x+3$, has a remainder which is divisible by 13. Once this is established, your rule of divisibility by 13 then follows if one plugs in $x=10$.

By Remainder Theorem, if $P(x)$ is divisible by $x+3$, then \begin{eqnarray} P(-3)=a_n(-3)^n+a_{n-1}(-3)^{n-1}+\cdots+a_1(-3)+a_0=0. \end{eqnarray} Let $y$ be the remainder of $Q(x)$ on division by $x+3$. Again by Remainder Theorem, \begin{eqnarray} Q(-3)=a_n(-3)^{n-1}+a_{n-1}(-3)^{n-2}+\cdots+a_2(-3)+a_1+4a_0=y. \end{eqnarray} We can easily see that \begin{eqnarray} -3y-P(-3)=-13a_0\\ 3y=13a_0. \end{eqnarray} Since both $y$ and $a_0$ are integers, and 3 and 13 are co-prime, $y$ is divisible by 13.

Are you asking how to prove this specific divisibility rule for $13$? If so, it's not hard with modulo arithmetic.

To separate the units place from the rest of the number, you can express it as $10x + y$, where $y$ represents the units place.

$10x + y = 13x - 3x + 13y - 12y = 13(x+y) -3(x+4y) \equiv -3(x+4y) \pmod{13}$

Since $3$ is coprime to $13$ (no factors other than $1$ in common), if $x+4y \equiv 0 \pmod{13}$ (another way of saying $x+4y$ is divisible by $13$), then $10x + y \equiv 0 \pmod{13}$, which proves the divisibility rule.

You can now express that rule in a simple algorithm: strip off the last digit, multiply it by $4$ and add that to the remaining number. If the new number is divisible by $13$, then so was the original number.

You can also find similar (i.e. slightly "ugly") rules for divisibility by $7$ and other odd primes using similar methods. For instance, for $7$, the rule is strip off the last digit, double it and subtract that from the remainder of the number. If the new number is divisible by $7$, so was the original. ($10x + y = 7(x+y) + 3(x-2y) \equiv 3(x-2y) \pmod 7$).