In primary and secondary school, you likely learned a number of algorithms for determining if one integer is divisible by another. There is a general algorithm that works in all cases, while there are also more efficient algorithms which only work in specific cases.

Problem 1.A: Determine if m divisible by n.

The general question is, how can you tell if an integer $m$ is divisible by another integer $n$?

The general algorithm is straight-forward:

Algorithm 1.A:

Input: a non-negative integer $m$ and a positive integer $n$.
Output: either 'yes' or 'no'.

To determine if a non-negative integer $m \ge 0$ is divisible by a positive integer $n > 0$, perform long division to calculate $m \div n$, and the remainder is zero if and only if $m$ is divisible by $n$.

This is because every integer $m$ can be written as $m = qn + r$ where $0 \le r < n$ and where $q$ is the quotient and $r$ is the remainder. $m$ is an integer multiple of $n$ if $m = qn$ for some value $q$.

There are, however, other algorithms that work in specific cases, which we will look at now. All of these depend on the number being written in base 10.

Is m divisible by 10, 100, 1000, etc?

This is the simplest problem: an integer $m$ is divisible by $10$, $100$ or $1000$ if the last digits are $0$, $00$ and $000$, respectively. In general, an integer $m$ is divisible by $10^k$ if the last $k$ digits are $0$.

Is m divisible by 2, 4, 8, etc?

The following are all algorithms that only work for specific values of $n$:

An integer is divisible by two if the last digit is divisible by two.

For example, $5838239$ is not divisible by two because $9$ is not divisible by two, while $858328$ is.

An integer is divisible by four if the last two digit are divisible by four.

For example, $58382382$ is not divisible by four because $82$ is not divisible by four, while $858328$ is.

An integer is divisible by eight if the last three digit are divisible by eight.

For example, $58382382$ is not divisible by eight because $382$ is not divisible by eight, while $858328$ is.

The general rule is: an integer is divisible by $2^k$ if the last $k$ digits are divisible by $k$.

What you probably never thought about is "why do these tricks work?"

The general rule is if $m = m_1 + m_2$ and $m_1$ is divisible by $n$, then $m$ is divisible by $n$ if and only if $m_2$ is divisible by $n$.

• The first works because $53247 = 53240 + 7$ and because $53240$ is a multiple of $10$, it must be divisible by two, so all we must do is determine if $7$ is divisible by two (which it isn't).
• The second works because $53247 = 53200 + 47$ and because $53200$ is a multiple of $100$, it must be divisible by four, so all we must do is determine if $47$ is divisible by four (which it isn't).
• Finally, we note that $53247 = 53000 + 247$ and because $53000$ is a multiple of $1000$, so because $247$ is not divisible by eight, neither is the larger.

Is m divisible by 5, 25, 125, etc?

Thus, we have similar rules:

• An integer is divisible by five if the last digit is divisible by five (either $0$ or $5$).
• An integer is divisible by $5^2 = 25$ if the last two digits are divisible by $25$ (either $00$, $25$, $50$ or $75$).
• An integer is divisible by $5^3 = 125$ if the last three digits are divisible by $125$ (either $000$, $125$, $250$ or $375$, $500$, $625$, $750$ or $875$).

Is m divisible by 3?

You may have learned additional tricks, such as:

An integer is divisible by three if the sum of the digits is divisible by three.

For example, to determine if $5838232$ is divisible by three, we calculate $5 + 8 + 3 + 8 + 2 + 3 + 2 = 31$. Now, how do we determine if $31$ is divisible by three? We calculate $3 + 1 = 4$, and we note that $4$ is not divisible by three, and thus $31$ is not divisible by three, and thus $5838232$ is not divisible by three.

This works for larger numbers as well, for example, $532523945623531349543623563210538255318828753209$ is divisible by three because $5+3+2+5+2+3+9+\cdots+2+0+9 = 198$, and $1 + 9 + 8 = 18$, and $1 + 8 = 9$ and $9$ is divisible by three.

This is actually an example of a recursive trick: we determine that the larger number is divisible by three if the sum of the digits is divisible by three; and we know the sum is divisible by three if the sum of its digits is divisible by three, and so on, until we get to a single digit, and only $3$, $6$ and $9$ are single-digit numbers that are divisible by three.

Now, as an engineering student, you should at the very least be wondering "Why does this algorithm work?" With a little bit of investigation, you should be able to determine this.

Is m divisible by 9 or 11?

Another algorithm is:

An integer is divisible by nine if the sum of the digits is divisible by nine.

An integer is divisible by eleven if the sum of the 1s digit minus the 10s digit plus the 100s digit minus the 1000s digit, etc., is divisible by eleven.

For example, $7063817253$ is not divisible by eleven because $3 - 5 + 2 - 7 + 1 - 8 + 3 - 6 + 0 - 7 = -24$, and $4 - 2 = 2$, which is not divisible by eleven, and thus the original number is not divisible by eleven.

On the other hand, $45597200053673929342$ is divisible by eleven because $2 - 4 + 3 - 9 + 2 - \cdots - 5 + 5 - 4 = -11$ and $1 - 1 = 0$ is divisible eleven.

Is m divisible by 8?

Above, you may have noted that it was necessary to determine if a three-digit number is divisible by eight. You may have learned the following trick that easily works for three-digit numbers:

An integer is divisible by eight if the 1s digit plus twice the 10s digit plus four times the 100s digit is divisible by eight.

Thus, for example, given $582$, we note $2 + 2 \cdot 8 + 4 \cdot 5 = 38$, and $8 + 2 \cdot 3 = 14$, so the original number is not divisible by eight.

Alternatively, $992$ is divisible by eight because $2 + 2\cdot 9 + 4 \cdot 9 = 56$, and $6 + 2\cdot 5 = 16$, and $6 + 2\cdot1 = 8$, which is divisible by eight.

Note that we can stop at the third digit, for from above we know that an integer is divisible by eight if and only if the last three digits are divisible by eight.

Is m divisible by 12?

Finally, as one last example, alternating the signs as we did with eleven, and increasing the multipliers by increasing powers of two will allow you to determine if an integer is divisible by twelve.

For example, $45599200053673929372$ is divisible by twelve because $2 - 2\cdot7 + 4\cdot3 - 8\cdot9 + 16\cdot2 - 32\cdot9 + \cdots + 262144 \cdot 5 - 524288 \cdot 4 = -1110024$, and $4 - 2\cdot2 + 4\cdot 4 + 16\cdot 1 - 32\cdot1 + 64\cdot 1 = 48$ and $8 - 2\cdot4 = 12$, which is divisible by twelve.

As you can see, this is not as useful as the trick for divisibility by 8, 9 or 11. It is much easier to determine if the number is divisible by three ($4 + 5 + 5 + 9 + \cdots + 7 + 2 = 90$ and $90 is divisible by three) and simultaneously divisible by four ($72$ is divisible by four).

Problems

1. Generalize the above algorithms to come up with an algorithm to determine if a number is divisible by seven or thirteen.

Summary

In summary, we have seen that there is one general algorithm that allows you to answer whether or not $n$ divides $m$, but there are also very specific algorithms that are tailored to determine if specific integers divide a given integer when the given integer is written in base 10.