1.3: Divisibility and the Division Algorithm

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

We now discuss the concept of divisibility and its properties.

Integer Divisibility

If \(a\) and \(b\) are integers such that \(a\neq 0\), then we say \(a\) divides \(b\) and write \(a\mid b\) if there exists an integer \(k\) such that \(b=ka\). That is, given \(a,b\in\ZZ\) such that \(a\neq 0\), we write \(a\mid b\) if \(\exists k\in\ZZ\). s.t. \(b=ka\).

If \(a\) divides \(b\), we also say \(a\) is a factor [or divisor] of \(b\), and \(b\) is a multiple of \(a\). If \(a\) does not divide \(b\), we write \(a\nmid b\).

Example \(\PageIndex{1}\)

For example, \(2\mid 4\) and \(7\mid 63\), while \(5\nmid 26\).

Definition: Word

Given \(a\in\ZZ\), we say \(a\) is even if \(2\mid a\), i.e., if \(\exists k\in\ZZ\) s.t. \(a=2k\). In contrast, given \(a\in\ZZ\), we say \(a\) is odd if \(2\nmid a\).

It is a consequence of the Division Algorithm, below, that if \(a\) is odd then \(\exists k\in\ZZ\) s.t. \(a=2k+1\).

Proposition \(\PageIndex{1}\)

\(\forall a\in\ZZ\) we have \(a\mid 0\).

Proposition \(\PageIndex{2}\)

If \(b\in\ZZ\) is such that \(|b|<a\), and \(b\neq 0\), then \(a\nmid b\).

Proposition \(\PageIndex{3}\)

Given \(a,b\in\ZZ\), \(a\mid b\Leftrightarrow a\mid|b|\).

Theorem \(\PageIndex{1}\)

If \(a, b\) and \(c\) are integers such that \(a\mid b\) and \(b\mid c\), then \(a\mid c\).

Proof

Since \(a\mid b\) and \(b\mid c\), we know \(\exists k_1, k_2\in\ZZ\) such that \(b=k_1a\) and \(c=k_2b\). Hence \(c=k_1k_2a\) and so \(a\mid c\).

Example \(\PageIndex{2}\)

Since \(6\mid 18\) and \(18\mid 36\), then \(6\mid 36\).

The following theorem states that if an integer divides two other integers then it divides any linear combination of these integers.

Theorem \(\PageIndex{2}\)

\(\forall a,b,c,m,n\in\ZZ\), if \(c\mid a\) and \(c\mid b\) then \(c\mid (ma+nb)\).

Proof

Since \(c\mid a\) and \(c\mid b\), \(\exists k_1, k_2\in\ZZ\) such that \(a=k_1c\) and \(b=k_2c\). Thus \[ma+nb=mk_1c+nk_2c=c(mk_1+nk_2),\] and hence \(c\mid (ma+nb)\).

Theorem 1.3.2 can be generalized to any finite linear combination as follows. If \[ n\in\NN,\ a,b_1,\dots,b_n\in\ZZ\text{ and }a\mid b_1, a\mid b_2,\dots,a\mid b_n\] then \[a\mid \sum_{j=1}^nk_jb_j\] \(\forall k_1,\dots,k_n\in\ZZ\). It would be a nice exercise to prove this generalization by induction.

The Division Algorithm

Theorem \(\PageIndex{3}\): The Division Algorithm

Given \(a,b\in\ZZ\) such that \(b>0\), there exist unique \(q,r\in\ZZ\) such that \(a=qb+r\) and \(0\leq r< b\). This \(q\) is called the quotient and \(r\) the remainder when \(a\) is divided by \(b\).

Proof

Consider the set \(A=\{a-bk\geq 0 \mid k\in \ZZ\}\). Note that \(A\) is nonempty since for \(k<a/b\), \(a-bk>0\). By the well-ordering principle, \(A\) has a least element \(r=a-qb\) for some \(q\in\ZZ\). Notice that \(r\geq 0\) by construction. Now if \(r\geq b\) then (since \(b>0\)) \[r>r-b=a-qb-b=a-(q+1)b\geq 0.\] This leads to a contradiction since \(r\) is assumed to be the least positive integer of the form \(r=a-qb\). As a result we have \(0\leq r<b\).

We will show that \(q\) and \(r\) are unique. Suppose that \(a=q_1b+r_1\) and \(a=q_2b+r_2\) with \(0\leq r_1<b\) and \(0\leq r_2<b\). Then we have \[a-a=q_1b+r_1-(q_2b+r_2)=(q_1-q_2)b+(r_1-r_2)=0.\] As a result we have \[(q_1-q_2)b=r_2-r_1.\] Thus we get that \[b\mid (r_2-r_1).\] And since \(-\max(r_1,r_2)\leq|r_2-r_1|\leq\max(r_1,r_2)\), and \(b>\max(r_1,r_2)\), then \(r_2-r_1\) must be \(0\), i.e. \(r_2=r_1\). And since \(bq_1+r_1=bq_2+r_2\), we also get that \(q_1=q_2\). This proves uniqueness.

Example \(\PageIndex{3}\)

If \(a=71\) and \(b=6\), then \(71=6\cdot 11+5\). Here \(q=11\) and \(r=5\).

Exercise \(\PageIndex{1}\)

1. Show that \(5\mid 25, 19\mid38\) and \(2\mid 98\).
2. Use the division algorithm to find the quotient and the remainder when 76 is divided by 13.
3. Use the division algorithm to find the quotient and the remainder when -100 is divided by 13.
4. Show that if \(a,b,c\) and \(d\) are integers with \(a\) and \(c\) nonzero, such that \(a\mid b\) and \(c\mid d\), then \(ac\mid bd\).
5. Show that if \(a\) and \(b\) are positive integers and \(a\mid b\), then \(a\leq b\).
6. Prove that the sum of two even integers is even, the sum of two odd integers is even and the sum of an even integer and an odd integer is odd.
7. Show that the product of two even integers is even, the product of two odd integers is odd and the product of an even integer and an odd integer is even.
8. Show that if \(m\) is an integer then \(3\) divides \(m^3-m\).
9. Show that the square of every odd integer is of the form \(8m+1\).
10. Show that the square of any integer is of the form \(3m\) or \(3m+1\) but not of the form \(3m+2\).
11. Show that if \(ac\mid bc\), then \(a\mid b\).
12. Show that if \(a\mid b\) and \(b\mid a\) then \(a=\pm b\).