# Finding divisibility rules [duplicate]

Find the divisibility test for 13.

Let's first find a test for small 3-digit numbers first and then find a general test. We'll be finding tests which involves separation of last digit. These tests will be similar to the tests of 19, 23, 29, etc.

Let $\overline { abc }$ be any number such that $\overline { abc } =100a+10b+c$. Now assume that $\overline { abc }$ is divisible by 13. Then

\begin{align} \overline { abc } &\equiv 0 \pmod{13}\\ 100a+10b+c &\equiv 0 \pmod{13}\\ 10\left( 10a+b \right) +c &\equiv 0 \pmod{13}\\ 10\overline { ab } +c &\equiv 0 \pmod{13}. \end{align}

Now that we have separated the last digit from the number, we have to find a way to use it:

What does coefficient of $\overline { ab }$ mean? And why does it have to be 1?

make the coefficient of $\overline { ab }$ 1.

In other words, we have to find an integer $n$ such that $10n\equiv 1 \bmod{13}$.

It can be observed that the smallest $n$ which satisfies this property is 4. Now we can multiply the original equation by 4 and simplify it:

\begin{align} 10\overline { ab } +c &\equiv 0 \pmod{13} \\ 40\overline { ab } +4c &\equiv 0 \pmod{13}\\ \overline { ab } +4c &\equiv 0 \pmod{13}. \end{align}

Aha! We have found out that if $\overline { abc } \equiv 0 \bmod{13},$ then $\overline { ab } +4c\equiv 0 \bmod{13}$. In other words, to check if a 3-digit number is divisible by 13, we can just remove the last digit, multiply it by 4, and then add it to the rest of the two digits.

Now that we have found out the test for 3-digit numbers, let's find out a general divisibility test. Let $\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 }{ x }_{ 1 } }$ be any $n$ digit number. Then

\begin{align} \overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 }{ x }_{ 1 } } &\equiv 0 \pmod{13}\\ 10\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +{ x }_{ 1 } &\equiv 0 \pmod{13}\\ 40\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 } &\equiv 0 \pmod{13}\\ \overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 } &\equiv 0 \pmod{13}. \end{align}

Hence, a number is a multiple of 13 if we add 4 times the last digit to the rest of the number and the resulting number is still divisible by 13. $_\square$

## marked as duplicate by Bill Dubuque divisibility StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 1 '17 at 16:51
Although you haven't asked a question, here is a quicker way to reach the same result. Using the division algorithm, write your number as $N=10m + d$ where $0\le d \le 9$.
Then $13 \mid N\iff 13 \mid 4N \iff 13\mid 40m+4d \iff 13\mid m+4d$
(The first equivalence in the chain follows because $4$ and $13$ are relatively prime.)