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

This question already has an answer here:

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

marked as duplicate by David K, Daniel W. Farlow, Shailesh, Namaste, Adam HughesDec 18 '16 at 2:01

• Please include / link a proof and tell us precisely what you don't follow. – Bill Dubuque Dec 16 '16 at 3:56
• I removed the "logic" tag - that refers to a specific field of mathematics, not general reasoning. – Noah Schweber Dec 16 '16 at 4:00
• A general version of divisibility rules of the type where we separate the last digit and then add/subtract a multiple of it to the integer formed by the rest of the digits is explained here. Together with a proof. I think that this is a duplicate, but I have promised not to instaclose... – Jyrki Lahtonen Dec 16 '16 at 4:48
• @JyrkiLahtonen I agree, so I started the mark-as-duplicate process the "normal" way. – David K Dec 17 '16 at 18:04

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$

• I am just getting my feet wet with number theory so bear with me as I've only stumbled upon this. I want to know why the if and only if statement holds true. thank you. – TheLast Cipher Sep 2 '17 at 4:27
• @The If $a,b$ are coprime then $\,a\mid bn\iff a\mid n\,$ by Euclid's Lemma (or by considering their unique prime factorizations). Or, more directly, notice that $\ 13\mid 4n\iff 13\mid n\$ by \ \begin{align}\bmod 13\!:\ n\equiv 0&\overset{\times\ 4}\Longrightarrow\,4n\equiv 0\\[.2em] 4n\equiv 0&\overset{\times (\color{#c00}{-3})}\Longrightarrow\ n\equiv 0 \end{align} where we scaled by the inverse of $\,4,\,$ i.e. $\,\dfrac{1}{4}\equiv \dfrac{-12}4\equiv\color{#c00}{-3}$ $\quad$ – Bill Dubuque Sep 2 '17 at 13:16
• is that supposed to be $-12n \equiv 0$? – TheLast Cipher Sep 2 '17 at 14:49
• @The No, we used $\ 1\equiv -12\pmod{\!13}\$ to make the division exact. – Bill Dubuque Sep 2 '17 at 14:54
• I found Deepak's answer more suited to me as a newbie. thank you for linking my question here! – TheLast Cipher Sep 2 '17 at 15:11

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