# law of divisibility on $37$

how to find and prove law of divisibility on $37$?

Added:---- how to prove for$37$ that: Split off the last digit, multiply by 11, and subtract the product from the number that is left. if the result is divisible by 37 then so is the original number.divisibility criteria for 37

-
define law of divisibility –  clark Apr 12 '13 at 18:39
@clark for example law of divisibility on 2 is the last digits of number must be even. –  agustin Apr 12 '13 at 18:41
so it should be an easier or faster process than doing the actual division ? –  clark Apr 12 '13 at 18:44
I guess you mean divisibility criterion, cut-the-knot.org/blue/divisibility.shtml –  leonbloy Apr 12 '13 at 18:45
Hint: $\rm 37\mid 10^3 - 1,\$ or note $\rm\: mod\ 37\!:\ 100\equiv -11,\:$ and $\rm\:{-11}^{-1}\equiv 10.$ –  Math Gems Apr 12 '13 at 18:46
show 1 more comment

As $$999=37\cdot27$$

So, $10^3\equiv1\pmod{37}\implies 10^{3k}\equiv1\pmod{37}$

So, $\sum_{0\le r\le n}a_i10^i$

$$=(a_0+10a_1+100a_2)+10^3(a_3+10a_4+100a_5)+10^6(a_6+10a_7+100a_8)\cdots$$

$$\equiv (a_0+10a_1+100a_2)+(a_3+10a_4+100a_5)+(a_6+10a_7+100a_8)\cdots\pmod {37}$$

i.e., we can group by $3$ digits and add to test the divisibility by $37$

EDIT: the explanation of the link in the Question

As $11\cdot(10a+b)-1\cdot(11b-a)=111\cdot a$

$(10a+b)$ will be divisible by $111\iff (11b-a)$ is divisible by $111$

A more general idea can be found here.

Try to find how $11,1$ are identified as multiplier from the link.

-

HINT: $37$ divides $999=37\cdot27$, so $37\equiv-1\pmod{1000}$. Now think about the classic divisibility test for $9\equiv-1\pmod{10}$. Imagine writing the number to be tested in base $1000$.

-

$\rm mod\ 37\!:\ 100^{-1}\!\equiv 10\:$ so  e.g. $\rm\:37\mid n = 100^2 c + 100 b + a \iff 37\mid 10^2 n \equiv c + 10 b + 10^2 a$

$37\mid \color{#0a0}{54}\color{blue}{39}\!:\quad \color{#0a0}{54}\!+\!10(\color{blue}{39}) \equiv \color{0a0}{17}\!+\!10(\color{blue}2)\equiv 0$

$\rm\!\begin{eqnarray} 37\mid \color{#0a0}{44}\color{blue}{47}\color{#c00}{40}\!: &&\!\!\color{#0a0}{44}\!+\!10(\color{blue}{47}\!+\!10(\color{#c00}{40}))\\ \equiv && \color{#0a0}7\!+\!10(\color{blue}{10}\!+\!10(\color{#c00}3))\\ \equiv && \color{#0a0}7\!+\!10(3)\equiv 0\end{eqnarray}$

$\rm\!\begin{eqnarray} 37\mid \color{#0a0}{54}\color{blue}{66}\color{#c00}{65}38\!: &&\color{#0a0}{54}\!+\!10(\color{blue}{66}\!+\!10(\color{#c00}{65}\!+\!10(38))) \\ \equiv && \color{#0a0}{17}\!+\!10(\color{blue}{29}\!+\!10(\color{#c00}{28}\!+\!10)) \\ \equiv && \color{#0a0}{17}\!+\!10(\color{blue}{29}\!+\!10)\\ \equiv &&\color{#0a0}{17}\!+\!10(2)\equiv 0 \end{eqnarray}$

-

Given a number in base 10, say $d_nd_{n-1}\cdots d_0$, calculate $d_0 + 10d_1+26d_2+d_3+10d4+26d_5+\cdots$ (alternating $1$, $10$, and $26$). The resulting number is divisible by 37 if and only if $d_nd_{n-1}\cdots d_0$ is divisible by $37$.

-

According to cross divisibility test (VJ's universal divisibility test )

if ty = 10a + b where GCD (a,b)=1

Then y | 10T +U if and only if y | (bT - aU )

Now 37*3 = 111 = 10a+ b => a = 11, b=1 also GCD (11, 1) =1

Therefore by cross divisibility test , 37 | (10T+ U) if and only if 37 | (T-11U)

Beside this , 37 | (10T+ U) if and only if 37 | (7T-3U)

To know "why it works?", read recently published research book 'Modern approach to speed math' at tinyurl.com/mlxk8pw . You can also find non recursive version of cross divisibility in book.

                              Regard,