Divisibility (and the Division Algorithm)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

The notion of divisibility is motivated and defined. We work through many examples and prove several simple divisibility lemmas –crucial for later theorems. We also discuss linear combinations and the division algorithm is presented and proven. The importance of the division algorithm is demonstrated through examples.

The process of division often relies on the long division method. The division algorithm, therefore, is more or less an approach that guarantees that the long division process is actually foolproof. Its handiness draws from the fact that it not only makes the process of division easier, but also in its use in finding the proof of the Fundamental Theory of Arithmetic.

We begin by stating the definition of divisibility, the main topic of discussion. We then give a few examples followed by several basic lemmas on divisibility. The Well-Ordering Axiom, which is used in the proof of the Division Algorithm, is then stated. Examples demonstrating how to use the Division Algorithm as a method of proof are then given.

Definition of Divisibility

Certainly the sum, difference and product of any two integers is an integer. The same can not be said about the ratio of two integers. For example, while 2 and 3 are integers, the ratio $2/3$ is not an integer. Thus, if we only wish to consider integers, we simply can not take any two integers and divide them. The study of the integers is to a great extent the study of divisibility.

Definition. If $a$ and $b$ are integers with $a\neq 0,$ we say that $a$ divides $b,$ written $a | b,$ if there exists an integer $c$ such that $b=a c.$

Here are some examples of divisibility

$3|6$ since $6=2(3)$ and $2\in \mathbb{Z}$

$6|24$ since $24=4(6)$ and $4\in \mathbb{Z}$

$8|0$ since $0=0(8)$ and $0\in \mathbb{Z}$

$-5|-55$ since $-55=11(-5)$ and $11\in \mathbb{Z}$

$-9|909$ since $909=-101(-9)$ and $-101\in \mathbb{Z}$

Other Common Ways

There are other common ways of saying $a$ divides $b.$ Namely, $a|b$ is equivalent to all of the following: $a$ is a divisor of $b,$ $a$ divides $b,$ $b$ is divisible by $a,$ $b$ is a multiple of $a,$ $a$ is a factor of $b$.

The division of integers is a direct process. For signed integers, the easiest and most preferred approach is to operate with their absolute values, and then apply the rules of sign division to determine the applicable sign. The rules of sign division says that the quotient of two positive or two negative integers is a positive integer, while that of a negative integer and a positive integer is a negative integer. Add some text here.

Any integer $n,$ except $0,$ has just a finite number of divisors. For if $a|n$ where $a$ and $n$ are positive integers, then $n=ak$ for some integer $k.$ Since $k$ is a positive integer, we see that $n=ak\geq a.$ Hence any nonzero integer $n$ can have at most $2|n|$ divisors.

Divisibility Lemmas

From the previous statement, it is clear that every integer must have at least two divisors, namely 1 and the number itself. Zero is divisible by any number except itself. Also, if it is possible to divide a number $m$, then it is equally possible to divide its negative. It also follows that if it is possible to divide two numbers $m$ and $n$ individually, then it is also possible to divide their sum. Add some text here.

We now state and prove the transitive and linear combination properties of divisibility.

Lemma. (Transitive Property of Divisibility) Let $a,$ $b,$ and $c$ be integers. If $a | b$ and $b | c,$ then $a | c.$

Proof. Suppose $a|b$ and $b|c,$ then there exists integers $m$ and $n$ such that $b=m a$ and $c=n b.$ Thus $$ c=n b=n(m a)=(n m )a.$$ Since $nm\in \mathbb{Z}$ we see that $a|c$ as desired.

We say an integer $n$ is a linear combination of $a$ and $b$ if there exists integers $x$ and $y$ such that $n=ax+by.$ For example, $7$ is a linear combination of $3$ and $2$ since $7=2(2)+1(3).$

The next lemma says that if an integer divides two other integers, then it divides any linear combination of these two integers.

Lemma. (Linear Combinations) Let $a,$ $b,$ and $c$ be integers. If $c|a$ and $c|b,$ then $c|(x a+y b)$ for any positive integers $x$ and $y.$

Proof. Suppose $c|a$ and $c|b.$ Then there exists integers $m$ and $n$ such that $a=m c$ and $b=n c.$ Assume $x$ and $y$ are arbitrary integers. We have $$ x a+y b=x(m c)+y(n c)= c(x m+ y n) $$ Since $x m+ y n \in \mathbb{Z}$ we see that $c|(x a+y b)$ as desired.

Properties of Divisibility

In addition to showing the divisibility relationship between any two non zero integers, it is worth noting that such relationships are characterized by certain properties. The properties of divisibility, as they are known in Number Theory, states that: 1. If a number $N$ is divisible by $m$, then it is also divisible by the factors of $m$; 2. If a number $N$ is divisible by both $p$ and $q$, where $p$ and $q$ are co-prime numbers, then $N$ is also divisible by the product of $p$ and $q$; 3. If a number $N$ is a factor of two number $s$ and $t$, then it is also a factor of the sum of and the difference between $s$ and $t$; and 4. When a number $N$ is a factor of another number $M$, then $N$ is also a factor of any other multiple of $M$.

Lemmas on Divisibility

We now state and prove the antisymmetric and multiplicative properties of divisibility.

Lemma. (Antisymmetric Property of Divisibility) Let $a$ and $b$ be nonzero positive integers. If $a | b$ and $b |a,$ then $a= b.$

Proof. Suppose $a|b$ and $b|a,$ then there exists integers $m$ and $n$ such that $b=m a$ and $a=n b.$ Notice that both $m$ and $n$ are positive since both $a$ and $b$ are. Then we have $$ a=n b= n(m a) = (n m) a. $$ Thus, $n m=1$ and so in particular $n= 1.$ Whence, $a= b$ as desired.

Lemma. (Multiplicative Property of Divisibility) Let $a,$ $b,$ and $c$ be integers. If $c\neq 0$ and $a|b$ then $a c|b c.$

Proof. Suppose $a|b.$ Then there exists an integer $n$ such that $b=n a.$ By substitution we find, $$ b c=(n c) a=(a c) n. $$ Since $c\neq 0,$ it follows that $ac\neq 0,$ and so $a c| b c$ as needed.

Lemma. Let $a$ and $b$ be integers. If $a|b,$ then $a^n|b^n$ for any natural number $n.$

Proof. We will use mathematical induction. Since $a|b$ certainly implies $a|b,$ the case for $k=1$ is trivial. Assume that $a^k|b^k$ holds for some natural number $k>1.$ Then there exists an integer $m$ such that $b^k=m a^k.$ Then \begin{align*} b^{k+1} & =b b^k =b \left(m a^k\right) \\ & =(b m )a^k =(m’ a m )a^k =M a^{k+1} \end{align*} where $m’$ and $M$ are integers. Whence, $a^{k+1}|b^{k+1}$ as desired.

The Well-Ordering Axiom

Before we state and prove the Division Algorithm, let’s recall the Well-Ordering Axiom, namely:

Every nonempty set of positive integers contains a least element.

This is an incredible important and powerful statement. We will use the Well-Ordering Axiom to prove the Division Algorithm.

The Division Algorithm

The proof of the Division Algorithm illustrates the technique of proving existence and uniqueness and relies upon the Well-Ordering Axiom.

Theorem. (Division Algorithm) If $a$ and $b$ are nonzero positive integers, then there are unique positive integers $q$ and $r$ such that $a=bq+r$ where $0\leq r < b.$

Proof. First we prove existence. Let $b$ be an arbitrary natural number greater than $0$ and let $S$ be the set of multiples of $b$ that are greater than $a,$ namely, $$ S=\{b i \mid i\in \mathbb{N} \text{ and } bi>a\}. $$ Notice $S$ is nonempty since $ab>a.$ By the Well-Ordering Axiom, $S$ must contain a least element, say $bk.$ Since $k\not= 0,$ there exists a natural number $q$ such that $k=q+1.$ Notice $b q\leq a$ since $bk$ is the least multiple of $b$ greater than $a.$ Thus there exists a natural number $r$ such that $a=bq+r.$ Notice $0\leq r.$ Assume, $r\geq b.$ Then there exists a natural number $m\geq 0$ such that $b+m=r.$ By substitution, $a=b(q+1)+m$ and so $bk=b(q+1)\leq a.$ This contradiction shows $r< b$ as needed.

Now we prove uniqueness. Suppose $$ a=bq_1 +r_1, \quad a=b q_2+r_2, \quad 0\leq r_1< b, \quad 0\leq r_2< b. $$ If $q_1=q_2$ then $r_1=r_2.$ Assume $q_1< q_2.$ Then $q_2=q_1+n$ for some natural number $n>0.$ This implies
$$ r_1=a-b q_1=bq_2+r_2-b q_1=b n +r_2\geq b n\geq b $$ which is contrary to $r_1< b.$ Thus $q_1< q_2$ cannot happen. Similarly, $q_2< q_1$ cannot happen either, and thus $q_1=q_2$ as desired.

Examples Using the Division Algorithm

We say an integer $a$ is of the form $bq+r$ if there exists integers $b,$ $q,$ and $r$ such that $a=bq+r.$ Notice that the division algorithm, in a certain sense, measures the divisibility of $a$ by $b$ using a remainder $r$.

Example. Show $3$ divides $a(a^2+2)$ for any natural number $a.$

Solution. Equivalently, we need to show that $a\left(a^2+2\right)$ is of the form $3k$ for some $k$ for any natural number $a.$ By the division algorithm, $a$ has exactly one of the forms $3 k,$ $3k+1,$ or $3k+2.$ If $a=3k+1$ for some $k,$ then $$ (3k+1)\left((3k+1)^2+2\right)=3(3k+1)\left(3k^2+2k+1\right) $$ which shows $3|a(a^2+2).$ If $a=3k+2$ for some $k,$ then $$ (3k+2) \left( (3k+2)^2+2\right)=3(3k+2)\left(3k^2+4k+2\right) $$ which shows $3|a(a^2+2).$ Finally, if $a$ is of the form $3k$ then we have $$ a \left(a^2+2\right) =3k\left(9k^2+2\right) $$ which shows $3|a(a^2+2).$ Therefore, in all possible cases, $3|a(a^2+2))$ for any positive natural number $a.$

Another Example Using the Division Algorithm

The advantage of the Division Algorithm is that it allows us to prove statements about the positive integers (integers) by considering only a finite number of cases. The next three examples illustrates this.

Example. Show $6$ divides the product of any three consecutive positive integers.

Solution. Let $m$ be an natural number. We need to show that $m(m+1)(m+2)$ is of the form $6 k.$ The division algorithm yields that $m$ is either even or odd. In either case, $m(m+1)(m+2)$ must be even. The natural number $m(m+1)(m+2)$ is also divisible by 3, since one of $m,$ $m+1,$ or $m+2$ is of the form $3k.$ Since $m(m+1)(m+2)$ is even and is divisible by 3, it must be divisible by 6.

Example. Prove that, for each natural number $n,$ $7^n-2^n$ is divisible by $5.$

Solution. Let $P$ be the set of natural number for which $7^n-2^n$ is divisible by $5.$ Clearly, $7^1-2^1=5$ is divisible by $5,$ so $P$ is nonempty with $0\in P.$ Assume $k\in P.$ We find \begin{align*} 7^{k+1}-2^{k+1} & = 7\cdot 7^k-2\cdot 2^k \\ & = 7\cdot 7^k-7\cdot 2^k+7\cdot 2^k-2\cdot 2^k \\ & = 7(7^k- 2^k)+2^k(7 -2) \end{align*} The induction hypothesis is that $(7^k- 2^k)$ is divisible by 5. Now since both $(7^k-\cdot 2^k)$ and $7-2$ are divisible by 5, so is any linear combination of $(7^k- 2^k)$ and $7-2.$ Hence, $7^{k+1}-2^{k+1}$ is divisible by 5. Therefore, $k+1\in P$ and so $P=\mathbb{N}$ by mathematical induction.

Exercises on Divisibility Part A

Exercise. Show that the sum of two even or two odd integers is even and also show that the sum of an odd and an even is odd.

Exercise. Show that the product of two odd integers is odd and also show that the product of two integers is even if either or one of them is even.

Exercise. Show that if $a$ and $b$ are positive integers and $a|b,$ then $a\leq b.$

Exercise. Show that if $a$ is an integer, then $3$ divides $a^3-a.$

Exercise. Show that the square of every of odd integer is of the form $8k+1.$

Exercise. Show that the product of every two integers of the form $6k+5$ is of the form $6k+1.$

Exercise. Find the number of positive integers not exceeding 1000 that are divisible by 3 but not by 4.

Exercise. Show that any integer of the form $6k+5$ is also of the form $3 j+2,$ but not conversely.

Exercise. Prove that if $a$ ad $b$ are integers, with $b>0,$ then there exists unique integers $q$ and $r$ satisfying $a=bq+r,$ where $2b\leq r < 3b.$

Exercises on Divisibility Part B

Exercise. Extend the Division Algorithm by allowing negative divisors. Specifically, prove that whenever $a$ and $b\neq 0$ are integers, there are unique integers $q$ and $r$ such that $a=bq+r,$ where $0\leq r < |b|.$

Exercise. Prove that the square of any integer is either of the form $3k$ or $3k+1.$

Exercise. Prove that the cube of any integer has one of the forms: $9k,$ $9k+1,$ $9k+8.$

Exercise. Prove that the cube of any integer has one of the forms: $7k,$ $7k+1,$ $7k-1.$

Exercise. Prove that the fourth power of any integer is either of the form $5k$ or $5k+1.$

Exercise. Let $a$ and $b$ be positive integers. Prove if $a|b,$ then $a^n|b^n$ for any positive integer $n.$

Exercises on Divisibility Part C

Exercise. Use mathematical induction to show that $n^5-n$ is divisible by 5 for every positive integer $n.$

Exercise. Prove that if $a,$ $b,$ and $c$ are integers with $a$ and $c$ nonzero, such that $a|b$ and $c|d,$ then $ac|bd.$

Exercise. Prove or disprove with a counterexample. There are integers $a,$ $b,$ and $c$ such that $a|bc,$ but $a\nmid b$ and $a\nmid c.$

Exercise. Prove or disprove with a counterexample. If $a,$ $b$ and $c\neq 0$ are integers, then $a|b$ if and only if $ac|bc.$

Exercise. Prove or disprove with a counterexample. If $a|m$ and $a|(ms+nt)$ for some integers $a\neq 0,$ $m,$ $s,$ $n,$ and $t,$ then $a|nt.$

Exercise. Prove that $7^n-1$ is divisible by $6$ for $n\geq 1.$

Exercise. Prove that $5^n-2^n$ is divisible by $3$ for $n\geq 1.$

Exercise. Show that $f_n\mid f_m$ when $n$ and $m$ are positive integers with $n\mid m.$

Exercise. Show that the product of every two integers of the form $6k+1$ is also of the form $6k+1.$

Exercise. Show that any integer of the form $6k+5$ is also of the form $3 k+2,$ but not conversely.

Exercise. Given nonzero integers $a, b,$ and $c$ show that $a|b$ and $a|c$ implies $a|(b x+c y)$ for any integers $x$ and $y.$

Leave a Comment