1.3: Divisibility and the Division Algorithm
( \newcommand{\kernel}{\mathrm{null}\,}\)
We now discuss the concept of divisibility and its properties.
Integer Divisibility
If a and b are integers such that a≠0, then we say a divides b and write a∣b if there exists an integer k such that b=ka. That is, given a,b∈Z such that a≠0, we write a∣b if ∃k∈Z. 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∤b.
Example 1.3.1
For example, 2∣4 and 7∣63, while 5∤26.
Definition: Word
Given a∈Z, we say a is even if 2∣a, i.e., if ∃k∈Z s.t. a=2k. In contrast, given a∈Z, we say a is odd if 2∤a.
It is a consequence of the Division Algorithm, below, that if a is odd then ∃k∈Z s.t. a=2k+1.
Proposition 1.3.1
∀a∈Z we have a∣0.
Proposition 1.3.2
If b∈Z is such that |b|<a, and b≠0, then a∤b.
Proposition 1.3.3
Given a,b∈Z, a∣b⇔a∣|b|.
Theorem 1.3.1
If a,b and c are integers such that a∣b and b∣c, then a∣c.
- Proof
-
Since a∣b and b∣c, we know ∃k1,k2∈Z such that b=k1a and c=k2b. Hence c=k1k2a and so a∣c.
Example 1.3.2
Since 6∣18 and 18∣36, then 6∣36.
The following theorem states that if an integer divides two other integers then it divides any linear combination of these integers.
Theorem 1.3.2
∀a,b,c,m,n∈Z, if c∣a and c∣b then c∣(ma+nb).
- Proof
-
Since c∣a and c∣b, ∃k1,k2∈Z such that a=k1c and b=k2c. Thus ma+nb=mk1c+nk2c=c(mk1+nk2), and hence c∣(ma+nb).
Theorem 1.3.2 can be generalized to any finite linear combination as follows. If n∈N, a,b1,…,bn∈Z and a∣b1,a∣b2,…,a∣bn then a∣n∑j=1kjbj ∀k1,…,kn∈Z. It would be a nice exercise to prove this generalization by induction.
The Division Algorithm
Theorem 1.3.3: The Division Algorithm
Given a,b∈Z such that b>0, there exist unique q,r∈Z such that a=qb+r and 0≤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≥0∣k∈Z}. 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∈Z. Notice that r≥0 by construction. Now if r≥b then (since b>0) r>r−b=a−qb−b=a−(q+1)b≥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≤r<b.
We will show that q and r are unique. Suppose that a=q1b+r1 and a=q2b+r2 with 0≤r1<b and 0≤r2<b. Then we have a−a=q1b+r1−(q2b+r2)=(q1−q2)b+(r1−r2)=0. As a result we have (q1−q2)b=r2−r1. Thus we get that b∣(r2−r1). And since −max(r1,r2)≤|r2−r1|≤max(r1,r2), and b>max(r1,r2), then r2−r1 must be 0, i.e. r2=r1. And since bq1+r1=bq2+r2, we also get that q1=q2. This proves uniqueness.
Example 1.3.3
If a=71 and b=6, then 71=6⋅11+5. Here q=11 and r=5.
Exercise 1.3.1
- Show that 5∣25,19∣38 and 2∣98.
- Use the division algorithm to find the quotient and the remainder when 76 is divided by 13.
- Use the division algorithm to find the quotient and the remainder when -100 is divided by 13.
- Show that if a,b,c and d are integers with a and c nonzero, such that a∣b and c∣d, then ac∣bd.
- Show that if a and b are positive integers and a∣b, then a≤b.
- 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.
- 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.
- Show that if m is an integer then 3 divides m3−m.
- Show that the square of every odd integer is of the form 8m+1.
- Show that the square of any integer is of the form 3m or 3m+1 but not of the form 3m+2.
- Show that if ac∣bc, then a∣b.
- Show that if a∣b and b∣a then a=±b.