# Better Divisibility by 8

Everywhere I look, when you want to see if something is divisible by $8$ then you see if the last $3$ digits are divisible by eight. But how do you know if the last $3$ digits are divisible by $8$? For example, I can't tell you immediately that $976$ is divisible by $8$. Is there a better algorithm for $8$-divisiblility or do I just need to get better at my arithmetic?

-
If you look, Wikipedia has a list of rules for divisibility by 8 Link – Silynn Jun 22 '14 at 4:25
If you can recognize on sight whether the number formed by the last two digits is divisible by $4$ and whether it is divisible by $8,$ then the original number is divisible by $8$ if either the hundreds digit is even and the number formed from the tens and ones digits is divisible by $8$ or if the hundreds digit is odd and the number formed from the tens and ones digits is divisible by $4$ but not $8.$ This works because (A) $100$ is divisible by $4$ but not $8,$ (B) $200$ is divisible by $8,$ (C) the sum of two numbers congruent to $4$ mod $8$ is divisible by $8.$ – Will Orrick Jun 22 '14 at 17:22
To emphasize Will Orrick's comment: you don't need to check whether 976 is divisible by 8 or not. Since 200 is divisible by 8, you can substract 200 from your number (multiple times) and check if the result is divisible by 8. So, for 976, you only need to check for 176. Better, it is sufficient to check for -24, which is obviously divisible by 8. – Taladris Jun 25 '14 at 10:08

For mental math, you want to keep taking out chunks until you get a remainder. For this to work, you need to have memorized the two-digit multiples of single-digit numbers. Looking at the first digit of $976$, we can take out the chunk $8$ out in front to get $176$. Next we need to incorporate the second digit, because $1$ is too small, so we're working with $17$. What's the biggest multiple of $8$ underneath $17$? Clearly $16$. So take out the chunk $16$ out of $17$ and we're left with $1$, then we tack on the $6$ to the right of it and we're looking at $16$, a known multiple of $8$, and we're done.

This is essentially long division, except you only keep track of a few digits of what you're doing at a time (easier for mental math) and you're only tracking the remainder, not the quotient. Further, in contrast to long division, you can subtract the number you're working with from even larger chunks if it speeds the process up (i.e. it reduces the digits faster). Here, as Hurkyl points out, you can subtract $976$ from $1000$ to get $24$ quickly. In these cases, for the larger chunks you'll usually want something that's easy to work with mentally. For mental subtraction from big multiples of $10$, I go digit-by-digit from the right, determining at each stage what I need to add to that digit to make it zero, and then carry a $1$ over to the next digit. So I need to add $4$ to $6$ to make that digit $0$, and then for the next digit I add $1$ to $7$ and determine I need to add $2$ to $8$ to make a $0$, so the remainder is $24$, which we know is a multiple of $8$.

-
Good chunk sizes are in my opinion 16, 40, 200, $10^n$ for $n > 2$ (that last part is why you can ignore all but the last three digits). You will probably come to choose your own favorite chunks as you do this more often, and the operation will become second nature (you almost certainly already have mechanical algorithms burnt into your brain for division by 3, 9, and perhaps 11) – Thomas Jun 22 '14 at 12:55
I like the idea of $1000 - 976$, it's much better than my instinct to halve 976 (that gives 488, which is not as readily obviously a multiple of 8 as 24 is, in my opinion). – Robert Soupe Jun 23 '14 at 3:08
@Robert I think it's easier to spot that 488 is a multiple of 8 (clearly 88 and 40 are, or 48 and 8) than it is to halve 976 mentally (which would require doing 450+35+3, if we're not going to subtract it from 1000). – blue Jun 23 '14 at 3:19
@blue That's kind of what I was saying, that's why I like your idea of subtraction: 488 looks more obvious but it takes more effort to get to it. – Robert Soupe Jun 23 '14 at 3:29
@Bill For what it's worth, I upvoted your answer but it's probably still gonna languish at the middle of the pack, unless the asker were to accept it. – Robert Soupe Jul 15 '14 at 1:25

With practice there are a lot of tricks to speed things up. For your example, knowing that 1000 is divisible by 8, I would immediately simplify the problem by reducing 976 to -24.

It's not too hard to memorize a few other intermediate values as well: I remember, for example, 128, 256, and 512 as multiples of 8, because they are powers of 2, and 800 is another obvious point.

The multiples of 200 would be good choices too, and probably the right things to remember to use: the only reason I used the other things is because they spring to mind first: I have to think about whether 200 is a multiple of 8.

-
This answer is probably the easiest answer, thank you. – Joao Jun 22 '14 at 4:32
@Joao There's an easier algorithm - see my answer. – Bill Dubuque Jul 14 '14 at 4:38

You can take the number formed by the last three digits, divide it by $2$, and then look the last two digits to see if it is divisible by $4$. So, $976/2 = 488$, and $88$ is divisible by $4$. Of course, this presumes that division by $2$ is mentally easier than division by $8$.

-
It can be done with $\,\le 2\,$ additions (of integers $\le 9),\,$ and $\,\le 3\,$ halvings (of integers $\,\le 15)\,$ - see my answer. – Bill Dubuque Jul 15 '14 at 1:47

We can use modular aritmethic to deduce a criteria. Let $a = a_n 10^n +\cdots + a_1 10 + a_0$, with $0 < a_i < 10 ~\forall ~i$ be a number represented in base $10$. Let's do a little list: \begin{align} 10^0 = 1 &\equiv 1 \mod 8 \\ 10 &\equiv 2 \mod 8 \\ 10^2 &\equiv 4 \mod 8 \\ 10^3 &\equiv 0 \mod 8 \\ 10^4 &\equiv 0 \mod 8 \\ \vdots\end{align} So, we can write: $$a = a_n 10^n +\cdots + a_1 10 + a_0 \equiv 4a_2 + 2a_1 + a_0 \mod 8$$

For example, $8 \not \mid12345$ because $8 \not \mid (5+2\times4+4\times3)=25$. You can do this to deduce criteria for numbers other than $8$.

-

For mental math the way I do it is this:

If the first digit of the three digit number is a multiple of $2$ (i.e. even), then I look at the last two digits and if they're a multiple of $8$, then the number is a multiple of $8$.

If the first digit of the number is not a multiple of $2$ (i.e. odd), then I look then I look at the last two digits, add $4$, and if the resulting number is a mutiple of $8$, then the number is a multiple of $8$.

e.g. for $224$ $$224 -> 24$$ $$24 \pmod 8 = 0$$ So $224$ is divisible by $8$.

For $368$ $$368 -> 68 + 4 = 72$$ $$72\pmod 8 = 0$$ So $368$ is divisible by $8$.

Like blue stated above, the key here is knowing the two digit multiples of the one digit multiple. I personally think my way is easier because it requires no division on your part. Just knowledge of your multiplication tables.

-

Hint $\,\ 8\mid abc \iff ((c/2+b)/2+a)/2\,$ yields integers for all quotients,

e.g. your $\,8\mid \color{#c00}9\color{#0af}7\color{#96f}6\,$ by $\smash[]{\underbrace{(\overbrace{(\color{#96f}6/2+\color{#0af}7)/2}^{\large =\,\color{#0af}5}+\color{#c00}9)/2}_{\large =\, \color{#c00}7}}\,$ has integer quotients $\,\color{#96f}3,\color{#0af}5,\color{#c00}7^{\phantom{I^{I^{I^{I^I}}}}}_\phantom{I^{I^{I^{I^I}}}}$

With practice the test takes only a few seconds of trivial mental arithmetic.

A proof is easy. Note $\ 8\mid c + 10 b + 10^2 a\iff 8\mid c + 2b + 2^2 a\$ since $\,10\equiv 2\pmod 8$

Further $\,\ nd\mid c + d\, e\iff d\mid c\ \ \&\ \ n\mid c/d + e.\,$ Iterating this yields said test

Lemma $\,\ d^3\!\mid c + d\,b + d^2 a\iff ((c/d + b)/d + a)/d\,$ yields integers for all quotients.

$\!\begin{eqnarray}{\bf Proof} && && d^{\,3}\!\mid\ c\, +\, d\,b + d^2 a\\ &\iff&\quad\ \ d\mid c &\ \&\ &d^{\,2}\!\mid\ c/d + b + d\, a\\ &\iff& \begin{array}{}\quad\ \ d\mid c\\ d\mid c/d+b\end{array}&\ \&\ &\ d\,\mid (c/d + b)/d+a\quad {\bf QED}\\\ \end{eqnarray}$

-

In base $10$ any number can be written as $$\sum_{r=0}^na_r10^r$$

which is $$\equiv a_0+10a_1+100a_2\pmod{1000}\equiv a_0+10a_1+100a_2\pmod8\equiv a_0+2a_1+4a_2$$

For $\displaystyle976, a_2=9,a_1=7,a_0=6\implies a_0+2a_1+4a_2=\cdots=56\equiv0\pmod8$

-