Divisibility Rules: An Introduction to Modular Arithmetic

There are many rules for determining whether a number is divisible by another. For example, we know that a number is even (divisible by 2) whenever the one’s digit is even. We also know that a number is divisible by 3 if the sum of its digits is divisible by 3. A less known one is the rule for divisibility by 11, which says that a number is divisible by 11 when the number obtained by starting with the one’s digit, subtracting the 10’s digit, adding the 100’s digit, and so on, alternating between adding and subtracting, until you’ve used all digits, is itself divisible by 11. For example, we know that 628474 is divisible by 11 because $4-7+4-8+2-6=-11$, which is divisible by 11. Indeed, the quotient of 628474 by 11 is 57134.

In this post, I will prove these rules to you while, at the same time, introducing a bit of elementary number theory, namely modular arithmetic.

To begin, I will prove a basic result about dividing integers.

Theorem. (Division Algorithm). Let $a$ and $b$ be integers, with $b>0$. Then, there exist unique integers $q$ (for quotient) and $r$ (for remainder) such that
\[
a = qb+r,
\]
where $0\leq r<b$.

Note: The proof method used here is a standard method in proofs about integers, using what is known as the Well-Ordering Principle. Basically, if you have a set of non-negative integers, then that set must has a smallest element. The proof of this is omitted, but it is highly recommended that the interested readers seek other resources for this material. I highly recommend David Burton’s text, Elementary Number Theory.

Proof.
Consider the set $S=\left\{a-bx\mid x\text{ is an integer and }a-bx\geq0\right\}$. (See: Footnote 1) We want to show that there is actually something in $S$. Now, since $b>0$, it follows that it must be at least 1, since it is an integer. Thus, $b|a|\geq|a|$ and so $a+b|a|\geq0$. Thus, $a-b\left(-|a|\right)$ is in $S$. Now, by the Well-Ordering Principle, this set must have a smallest element $r\geq0$. By the definition of $S$, this means that there is an integer $q$ so that $r=a-qb$. If $r\geq b$, then $a-\left(q+1\right)b=\left(a-qb\right)-b=r-b\geq 0$, which makes $r-bQED

Footnotes
1: For now, just think of a set as a collection of things that satisfy certain properties. I will make a post in the near future which will explain why this is technically not the correct way to look at it, but those subtle issues do not arise here.
2: The $’$ (prime) notation does not mean derivative. It is just a means to distinguish them from the original $q$ and $r$.

Don’t worry if you had trouble with understanding this proof. Just read and reread it a few times if you’d like to understand it, or just move forward accepting it by faith.
An immediate consequence to this theorem is a slightly more general version. I leave it to the reader to see why it should be obvious.

Corollary. (Division Algorithm). Let $a$ and $b$ be integers, with $b\neq0$. Then, there exist unique integers $q$ (for quotient) and $r$ (for remainder) such that
\[
a = qb+r,
\]
where $0\leq r<|b|$. Definition. Let $a$ and $b$ be integers, $b\neq0$. We say that $b\mid a$, read “$b$ divides $a$”, if $a=qb$ for some integer $q$. That is, when dividing $a$ by $b$, there will be no remainder.

There are a few facts to prove for this.

Theorem. Let $a,b,c$ be integers. Then,

  1. $a\mid0,\;\;1\mid a,\;\;a\mid a$ (Last property: Reflexive property),
  2. $a\mid1$ if and only if $a=\pm1$,
  3. If $a\mid b$ and $c\mid d$, then $ac\mid bd$,
  4. (Transitive property): If $a\mid b$ and $b\mid c$, then $a\mid c$,
  5. (Almost Antisymmetric property): $a\mid b$ and $b\mid a$ if and only if $a=\pm b$,
  6. If $a\mid b$ and $b\neq0$, then $|a|\leq |b|$, and
  7. If $a\mid b$ and $a\mid c$, then $a\mid\left(bx+cy\right)$ for all integers $x,y$.

Proof.
This is left as an exercise for the reader. The last two may be the trickiest ones, but are still not hard. The active and interested readers would do well to prove these before moving on, as getting one’s hands dirty allows for a more deep understanding than just spectating.
QED

Finally, it is time to introduce modular arithmetic.

Definition. Let $a,b,$ and $n$ be integers. We say that $a\equiv b\,\left(\text{mod}\,n\right)$, read “$a$ is congruent to $b$ modulo $n$”, if $n\mid a-b$. Basically, the standard value for $b$ will be the remainder of $a$ after dividing by $n$ using the division algorithm. That is, if $a=qn+r$, then $a\equiv r\,\left(\text{mod}\,n\right)$.

From this definition comes another set of basic properties whose proofs are left to the reader. After these, we will finally get to the important details of this post.

Theorem. Let $n>1$ and $a,b,c,d$ be integers. Then,

  1. (Reflexive property): $a\equiv a\,\left(\text{mod}\,n\right)$,
  2. (Symmetric property): If $a\equiv b\,\left(\text{mod}\,n\right)$, then $b\equiv a\,\left(\text{mod}\,n\right)$,
  3. (Transitive property): If $a\equiv b\,\left(\text{mod}\,n\right)$ and $b\equiv c\,\left(\text{mod}\,n\right)$, then $a\equiv c\,\left(\text{mod}\,n\right)$,
  4. If $a\equiv b\,\left(\text{mod}\,n\right)$ and $c\equiv d\,\left(\text{mod}\,n\right)$, then $a+c\equiv b+d\,\left(\text{mod}\,n\right)$ and $ac\equiv bd\,\left(\text{mod}\,n\right)$,
  5. If $a\equiv b\,\left(\text{mod}\,n\right)$, then $a+c\equiv b+c\,\left(\text{mod}\,n\right)$ and $ac\equiv bc\,\left(\text{mod}\,n\right)$, and
  6. If $a\equiv b\,\left(\text{mod}\,n\right)$, then $a^k\equiv b^k\,\left(\text{mod}\,n\right)$ for any positive integer $k$.

Note: Properties (1)-(3) define what is known as an equivalence relation. Essentially, two things that are congruent modulo $n$ are considered “basically the same” in this context.
Proof Hint: Be sure to keep the properties of divisibility above as well as the definition of congruence (modulo n) in mind.

We will make ample use of all of these properties from now on.

Divisibility by 2: Note that any integer is congruent to either 0 or 1 modulo 2. This is because all integers will have remainder 0 (if even) or 1 (if odd) when divided by $2$. Now, suppose we have an integer $a=a_na_{n-1}\cdots a_1a_0$, where each $a_i$ is a digit (that is, $0\leq a_i\leq9$ for all indices $i$). We may rewrite this as $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0$ (from now on, I will go to this step immediately). Then, since $10\equiv 0\,\left(\text{mod}\,2\right)$, this means that $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0\equiv a_n\cdot0+a_{n-1}\cdot0+\cdots+a_1\cdot0+a_0\equiv a_0\,\left(\text{mod}\,2\right)$. Therefore, the integer $a$ is divisible by 2 if and only if its one’s digit is divisible by 2, as we all have learned since first learning about division.
Example: We know that 11314654 is divisible by 2 because 4 is divisible by 2. After a little long division, one sees that the quotient is 5657327.

Divisibility by $2^k$: An even stronger property can be made. Rather than just 2, we can look at any power of 2 for a positive integer $k$. I leave it to the reader to convince themselves that $2^k\mid a$ if and only if $2^k$ divides the last $k$ digits of $a$. Hint: $10^n\equiv0\,\left(\text{mod}\,2^k\right)$ for all integers $n\geq k$.
Example: We know that 9528064 is divisible by 8 because 64 is divisible by 8 (the 0 before 64 is implicit). After a little long division, one sees that the quotient is 1191008.

Divisibility by 3 and 9: In this case, note that $10=3\cdot3+1$, and so $10\equiv1\,\left(\text{mod}\,3\right)$. Now, suppose we have an integer $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0$. Then, we have that $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0\equiv a_n\cdot1+a_{n-1}\cdot1+\cdots+a_1\cdot1+a_0\equiv a_n+a_{n-1}+\cdots+a_1+a_0\,\left(\text{mod}\,3\right)$. Therefore, $3\mid a$ if and only if 3 divides the sum of the digits of $a$. A similar result happens for 9 because, again, $10\equiv1\,\left(\text{mod}\,9\right)$.
Examples: We know that 56541 is divisible by 3 because 5+6+5+4+1=21 which is divisible by 3. However, this is not divisible by 9, because 21 is not. Indeed, the quotient by 3 is 18847, but $56541=56538+3$, and so there is a remainder of 3 if we divide by 9. A number which is divisible by 9 is 169623.

Divisibility by 5 and $5^k$: Since $10\equiv0\,\left(\text{mod}\,5\right)$, we use the same argument as with 2 to show that $5\mid a$ if and only if $5\mid a_0$, and so the only possible values of $a_0$ are 0 and 5, since $0\leq a_0 \leq9$. Similarly, $5^k\mid a$ if and only if the last $k$ digits of $a$ are divisible by $5^k$ for any positive integer $k$.
Example: 24534640 is divisible by 5 because 0 is. The quotient is 4906928.

Divisibility by $11$: This is the last rule that I will discuss. Since $10=11\cdot1-1$, we have that $10\equiv-1\,\left(\text{mod}\,11\right)$. Now, suppose we have an integer $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0$. Then, we have that $a=a_n\cdot10^n + a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0\equiv a_n\cdot\left(-1\right)^n+a_{n-1}\cdot\left(-1\right)^{n-1}+\cdots-a_1+a_0\equiv a_0-a_1+a_2-a_3+\cdots+\left(-1\right)^{n-1}a_{n-1}+\left(-1\right)^na_n\,\left(\text{mod}\,11\right)$. Therefore, $11\mid a$ if and only if the alternating addition/subtraction of the digits of $a$ is divisible by 11.
Example: 9849848 is not divisible by 11 because 8-4+8-9+4-8+9 = 8. However, we can fix this because we know that putting an 8 in front will give 89849848 and 8-4+8-9+4-8+9-8=0 which is divisible by 11. Similarly, we may put a 30 in front to get 309849848, which is divisible by 11 because 8-4+8-9+4-8+9-0+3=11. The quotient of 89849848 by 11 is 8168168, and the quotient of 309849848 by 11 is 28168168.

I end this post with a couple of exercises:

  1. Go through these proofs of divisibility rules and list each place where a divisibility and/or congruence property is implicitly used, making sure to list which property it is each time.
  2. Determine rules for other integers. Is there an easy rule for divisibility by 7? How about $7^k$ or $11^k$ for all positive integers $k$? What about larger integers?

P.S.: Yes, Randy, $2+2\equiv0\,\left(\text{mod}\,4\right)$.

This entry was posted in Basic Facts, Elementary Number Theory. Bookmark the permalink.