Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 a0, then we say a divides b and write ab if there exists an integer k such that b=ka. That is, given a,bZ such that a0, we write ab if kZ. 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 ab.

Example 1.3.1

For example, 24 and 763, while 526.

Definition: Word

Given aZ, we say a is even if 2a, i.e., if kZ s.t. a=2k. In contrast, given aZ, we say a is odd if 2a.

It is a consequence of the Division Algorithm, below, that if a is odd then kZ s.t. a=2k+1.

Proposition 1.3.1

aZ we have a0.

Proposition 1.3.2

If bZ is such that |b|<a, and b0, then ab.

Proposition 1.3.3

Given a,bZ, aba|b|.

Theorem 1.3.1

If a,b and c are integers such that ab and bc, then ac.

Proof

Since ab and bc, we know k1,k2Z such that b=k1a and c=k2b. Hence c=k1k2a and so ac.

Example 1.3.2

Since 618 and 1836, then 636.

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,nZ, if ca and cb then c(ma+nb).

Proof

Since ca and cb, k1,k2Z 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 nN, a,b1,,bnZ and ab1,ab2,,abn then anj=1kjbj k1,,knZ. It would be a nice exercise to prove this generalization by induction.

The Division Algorithm

Theorem 1.3.3: The Division Algorithm

Given a,bZ such that b>0, there exist unique q,rZ such that a=qb+r and 0r<b. This q is called the quotient and r the remainder when a is divided by b.

Proof

Consider the set A={abk0kZ}. Note that A is nonempty since for k<a/b, abk>0. By the well-ordering principle, A has a least element r=aqb for some qZ. Notice that r0 by construction. Now if rb then (since b>0) r>rb=aqbb=a(q+1)b0. This leads to a contradiction since r is assumed to be the least positive integer of the form r=aqb. As a result we have 0r<b.

We will show that q and r are unique. Suppose that a=q1b+r1 and a=q2b+r2 with 0r1<b and 0r2<b. Then we have aa=q1b+r1(q2b+r2)=(q1q2)b+(r1r2)=0. As a result we have (q1q2)b=r2r1. Thus we get that b(r2r1). And since max(r1,r2)|r2r1|max(r1,r2), and b>max(r1,r2), then r2r1 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=611+5. Here q=11 and r=5.

Exercise 1.3.1

  1. Show that 525,1938 and 298.
  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 ab and cd, then acbd.
  5. Show that if a and b are positive integers and ab, then ab.
  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 m3m.
  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 acbc, then ab.
  12. Show that if ab and ba then a=±b.

This page titled 1.3: Divisibility and the Division Algorithm is shared under a CC BY-SA license and was authored, remixed, and/or curated by Jonathan A. Poritz.

Support Center

How can we help?