# What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?

-
Do you mean if its divisible by 57? Its remainder? The present statement is unclear; the question should be edited to clarify this. (You'll also want to switch the tag from number-theory to elementary-number-theory; the former isn't really suitable. The divisibility and modular-arithmetic tags may also be advisable.) – Semiclassical Aug 19 '14 at 14:02
@Semiclassical : murderousmaths.co.uk/books/bkmm1x11.htm the same ideas but for 57 – Kumar Aug 19 '14 at 14:04
Seems it must be "divisible by 57", and that the use of "divided" in the question can be explained by language problem. – coffeemath Aug 19 '14 at 14:05
thanks @coffeemath – Kumar Aug 19 '14 at 14:06
Note that $57=3\cdot 19$. It's easy to tell if a number is divisible by $3$ (sum its digits, sum the digits of that, etc. until you can tell whether you're getting multiples of three). So the only tricky thing is finding a divisibility rule for 19. Also, note that the Chinese remainder theorem is applicable for dealing with the remainder of division by 57. – Semiclassical Aug 19 '14 at 14:10

As noted in the comments, $n$ is divisible by $57$ if and only if $n$ is divisible by $3$ and by $19$.

Divisibility test for $3$ is well known (as noted by Semiclassical above): Just see if the sum of the digits is divisible by $3$.

Divisibility test for $19$: Take the last digit of $n$ and double it. Add this result to what is left of $n$ after removing the last digit. Your original number is divisible by $19$ if and only if your final answer is divisible by $19$.

Reasoning: Write $n=10a+b$ where $b$ is a $1$-digit number. We have: $$19\mid 10a+b \Leftrightarrow 19\mid 10a+b+19b \Leftrightarrow 19\mid 10a+20b\Leftrightarrow 19\mid a+2b$$ (last follows since $10$ and $19$ are relatively prime).

For longer numbers, apply the rule as many times as necessary.

Example: $n=2137$. $213+2\cdot 7=227$. $22+2\cdot 7=36$. So $2137$ is not divisible by $19$.

(Note: Divisibility tests here assume that $n$ is expressed in base 10).

-
To speed up a little, you can chop off the last two digits, and multiply by 4 instead. – Michael Aug 19 '14 at 15:25

To check divisibility by $57$ you simply check divisibility by $3$ and $19$.

If you are familiar with modular arithmetic, use the fact that

$$20 \equiv 1 \pmod{19}$$ Therefore, if you have a number $n$ add the last 2 digits with 5 times the rest and repeat. $n$ is divisible by $19$ if and only if any of the numbers you get is divisible by $19$.

$$300000177 \rightarrow 77+5*3000001=15000082 \to 82+5*150000=750082 \to 82+5*7500=37582 \to 82+5*375=1957 \to 57+5*19$$ as both 57 and 19 are divisible by 19, the original number is also divisible by 19.

If you want directly a divisibility rule by $57$, use that $399$ is a multiple of 57. Therefore $$400 \equiv 1 \pmod{57}$$

this leads to a similar more complicated rule.

Added $20 \equiv 1 \pmod{19}$ means $100 \equiv 5 \pmod{19}$. Write $n =100 a+b$. Then $$n =100a+b \equiv 5a+b \pmod{19}$$

-
This is nice, but can you elaborate a little more how the fact that $20 \equiv 1 \pmod {19}$ leads to that divisibility criterion? – Ant Aug 19 '14 at 14:37
@Ant Done...... – N. S. Aug 19 '14 at 14:58
Easier: $\ 7)\!\underset{\equiv 14}2\!\!+7)\underset{\equiv 4}2\!+1)\!\underset{\equiv 10}2\!\!+0)\underset{\equiv 1}2\!+0)\underset{\equiv 2}2\!+0)\underset{\equiv 4}2\!+0)\underset{\equiv 8}2\!+0)\!\underset{\equiv 16}2\!\!+3\equiv 0\pmod{19},\,$ which uses only very simple mental arithmetic (doubling and adding a single digit,  mod $\,19),\,$ see my answer. – Bill Dubuque Aug 19 '14 at 15:32

$5+7=12=3\cdot4$, so divisibility by $57$ implies being a multiple of $3$. Since $3+1+7+7=18=$ $=3\cdot6$, your number meets this demand, the other being divisibility by $19$. Since $100=5\cdot20=$ $=5(19+1)$, your number is divisible by $19$ if $77\cdot5^0+01\cdot5^1+00\cdot5^2+00\cdot5^3+3\cdot5^4=77+$ $+5+3\cdot625=82+1875=1957=19\cdot103$ is a multiple of $19$, which is indeed the case.

-

Hint $\ \ 3\mid n\iff\,$ the sum of the decimal digits of $\,n\,$ is $\,\equiv 0\pmod 3,\,$ by $\,10\equiv 1\pmod 3$

and $\ \ \ 19\mid n\iff 19\,$ divides the reversed digit number in radix $2\,$ (binary),  since, e.g.

$\!\!\!\begin{eqnarray} &&19\mid\ \ d_3 10^3\! + d_2 10^2\! + d_1 10 + d_0\\ \iff &&19\mid (d_3 10^3\! + d_2 10^2\! + d_1 10 + d_0)\, 2^3\ \ {\rm by}\ \ (19,2) = 1. \ \text{ Thus, using} \ \, 20\equiv 1\!\!\!\pmod{19}\\ \iff &&19\mid\ d_3 + d_2 2 + d_1 2^2 + d_0 2^3 = \text{ reversed number in binary}\\ \iff &&19\mid\ d_3 + 2(d_2 + 2(d_1 + 2 d_0))\ \ \text{in Horner form} \end{eqnarray}$

e.g. $\quad\! 19\mid 5016\$ by $\ 6)\!\underset{\equiv\color{#0a0}{ 12}}{2}\!\!\color{#c0F}{+1})\underset{\equiv \color{#c00}7}2\!+ 0)\!\underset{\equiv 14}2\!+5\equiv 0\pmod{19}\$ takes only $\,5\,$ secs mentally.

$\equiv n$ is partial eval: $\,(6)2\equiv \color{#0a0}{12},\,$ next $\,(\color{#0a0}{12}\!\color{#c0f}{+\!1})2\equiv\color{#c00} 7,\ \ldots$

-

Number is divisible by 57 if the sum of '4 times hundreds + last two digit' is divisible by 57. For more detail about cross divisibility test refer Divisibility criteria for $7,11,13,17,19$

-