Processing math: 44%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.3: Divisibility

( \newcommand{\kernel}{\mathrm{null}\,}\)

In this section, we shall study the concept of divisibility. Let a and b be two integers such that a0. The following statements are equivalent:

  • a divides b,
  • a is a divisor of b,
  • a is a factor of b,
  • b is a multiple of a, and
  • b is divisible by a.

They all mean

There exists an integer q such that b=aq

In terms of division, we say that a divides b if and only if the remainder is zero when b is divided by a. We adopt the notation ab[pronounced as "a divides b''] Do not use a forward slash / or a backward slash in the notation. To say that a does not divide b, we add a slash across the vertical bar, as in

ab[pronounced as "a does not divide b''] Do not confuse the notation ab with ab. The notation ab represents a fraction. It is also written as a/b with a (forward) slash. It uses floating-point (that is, real or decimal) division. For example, 114=2.75.

The definition of divisibility is very important. Many students fail to finish very simple proofs because they cannot recall the definition. So here we go again:

abb=aq for some integer q.

Both integers a and b can be positive or negative, and b could even be 0. The only restriction is a0. In addition, q must be an integer. For instance, 3=232, but it is certainly absurd to say that 2 divides 3.

Example 5.3.1

Since 14=(2)(7), it is clear that 214.

hands-on exercise 5.3.1

Verify that 535,835,2535,714,214,and1414, by finding the quotient q and the remainder r such that b=aq+r, and r=0 if ab.

Example 5.3.2

An integer is even if and only if it is divisible by 2, and it is odd if and only if it is not divisible by 2.

hands-on exercise 5.3.2

What is the remainder when an odd integer is divided by 2? Complete the following sentences:

  • If n is even, then n=\bline0.5in for some integer  .

  • If n is odd, then n=\bline0.5in for  .

Memorize them well, as you will use them frequently in this course.

hands-on exercise 5.3.3

Complete the following sentence:

  • If n is not divisible by 3, then n=\bline0.5in, or n=\bline0.5in, for some integer  .

Compare this to the \bdiv and mod operations. What are the possible values of nmod3?

Example 5.3.3

Given any integer a0, we always have a0 because 0=a0. In particular, 0 is divisible by 2, hence, it is considered an even integer.

Example 5.3.4

Similarly, ±1 and ±b divide b for any nonzero integer b. They are called the trivial divisors of a. A divisor of b that is not a trivial divisor is called a nontrivial divisor of b.

For example, the integer 15 has eight divisors: \pm1, \pm3, \pm5, \pm15. Its trivial divisors are \pm1 and \pm15, and the nontrivial divisors are \pm3 and \pm5.

Definition

A positive integer a is a proper divisor of b if a\mid b and a<|b|. If a is a proper divisor of b, we say that a divides b properly.

Remark

Some number theorists include negative numbers as proper divisors. In this convention, a is a proper divisor of b if a\mid b, and |a|<|b|. To add to the confusion, some number theorists exclude \pm1 as proper divisors. Use caution when you encounter these terms.

Example \PageIndex{5}\label{eg:divides-05}

It is clear that 12 divides 132 properly, and 2 divides -14 properly as well. The integer 11 has no proper divisor.

hands-on exercise \PageIndex{4}\label{he:divides-04}

What are the proper divisors of 132?

Definition

An integer p>1 is a prime if its positive divisors are 1 and p itself. Any integer greater than 1 that is not a prime is called composite.

Remark

A positive integer n is composite if it has a divisor d that satisfies 1<d<n. Also, according to the definition, the integer 1 is neither prime nor composite.

Example \PageIndex{6}\label{eg:divides-06}

The integers 2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\, are primes.

hands-on exercise \PageIndex{5}\label{he:divides-07}

What are the next five primes after 23?

Theorem \PageIndex{1}

There are infinitely many primes.

Proof

We postpone its proof to a later section, after we prove a fundamental result in number theory.

Theorem \PageIndex{2}

For all integers a, b, and c where a \neq 0, we have

  1. If a\mid b, then a\mid xb for any integer x.

  2. If a\mid b and b\mid c, then a\mid c. (This is called the transitive property of divisibility.)

  3. If a\mid b and a\mid c, then a\mid (sb+tc) for any integers x and y. (The expression sb+tc is called a linear combination of b and c.)

  4. If b\neq 0 and a\mid b and b\mid a, then a = \pm b.

  5. If a\mid b and a,b > 0, then a \leq b.

Proof

We shall only prove (1), (4), and (5), and leave the proofs of (2) and (3) as exercises.

Proof of (1)

Assume a\mid b, then there exists an integer q such that b=aq. For any integer x, we have xb = x\cdot aq = a \cdot xq, where xq is an integer. Hence, a\mid xb.

Proof of (4)

Assume a\mid b, and b\mid a. Then there exist integers q and q' such that b=aq, and a=bq'. It follows that a = bq' = aq\cdot q'. This implies that qq'=1. Both q and q' are integers. Thus, each of them must be either 1 or -1, which makes b=\pm a.

Proof of (5)

Assume a\mid b and a,b>0. Then b=aq for some integer q. Since a,b>0, we also have q>0. Being an integer, we must have q\geq1. Then b = aq \geq a\cdot 1 = a.

Example \PageIndex{7}\label{eg:divides-07}

Use the definition of divisibility to show that given any integers a, b, and c, where a\neq0, if a\mid b and a\mid c, then a\mid(sb^2+tc^2) for any integers s and t.

Solution

We try to prove it from first principles, that is, using only the definition of divisibility. Here is the complete proof.

Assume a\mid b and a\mid c. There exist integers x and y
such that b=ax and c=ay. Then
sb^2+tc^2 = s(ax)^2+t(ay)^2 = a(sax^2+tay^2),
where sax^2+tay^2 is an integer. Hence a\mid(sb^2+tc^2).

The key step is substituting b=ax and c=ay into the expression sb^2+tc^2. You may ask, how can we know this is the right thing to do?

Here is the reason. We want to show that a\mid(sb^2+tc^2). This means we need to find an integer which, when multiplied by a, yields sb^2+tc^2. This calls for writing sb^2+tc^2 as a product of a and another integer that is yet to be determined. Since s and t bear no relationship to a, our only hope lies in b and c. We do know that b=ax and c=ay, therefore, we should substitute them into sb^2+tc^2.

hands-on exercise \PageIndex{6}\label{he:divides-06}

Let a, b, and c be integers such that a\neq 0. Prove that if a\mid b or a\mid c, then a\mid bc.

Summary and Review

  • An integer b is divisible by a nonzero integer a if and only if there exists an integer q such that b=aq.
  • An integer n>1 is said to be prime if its only divisors are \pm1 and \pm n; otherwise, we say that n is composite.
  • If a positive integer n is composite, it has a proper divisor d that satisfies the inequality 1<d<n.

Exercise \PageIndex{1}\label{ex:divides-01}

Let a, b, and c be integers such that a\neq0. Use the definition of divisibility to prove that if a\mid b and c\mid (-a), then (-c)\mid b. Use only the definition of divisibility to prove these implications.

Exercise \PageIndex{2}\label{ex:divides-02}

Let a, b, c, and d be integers with a,c\neq0. Prove that

  • If a\mid b and c\mid d, then ac\mid bd.
  • If ac \mid bc, then a\mid b.

Exercise \PageIndex{3}\label{ex:divides-03}

Let a, b, and c be integers such that a,b\neq0. Prove that if a\mid b and b\mid c, then a\mid c.

Exercise \PageIndex{4}\label{ex:divides-04}

Let a, b, and c be integers such that a\neq0. Prove that if a\mid b and a\mid c, then a\mid (sb+tc) for any integers s and t.

Exercise \PageIndex{5}\label{ex:divides-05}

Prove that if n is an odd integer, then n^2-1 is divisible by 4.

Exercise \PageIndex{6}\label{ex:divides-06}

Use the result from Problem [ex:divides-05] to show that none of the numbers 11, 111, 1111, and 11111 is a perfect square. Generalize, and prove your conjecture.

Hint

Let x be one of these numbers. Suppose x is a perfect square, then x=n^2 for some integer n. How can you apply the result from Problem [ex:divides-05]?

Exercise \PageIndex{7}\label{ex:divides-07}

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

Exercise \PageIndex{8}\label{ex:divides-08}

Use Problem [ex:divides-07] to prove that 3m^2-1 is not a perfect square for any integer m.

Exercise \PageIndex{9}\label{ex:divides-09}

Use induction to prove that 3\mid (2^{2n}-1) for all integers n\geq1.

Exercise \PageIndex{10}\label{ex:divides-10}

Use induction to prove that 8\mid (5^{2n}+7) for all integers n\geq1.

Exercise \PageIndex{11}\label{ex:divides-11}

Use induction to prove that 5\mid (n^5-n) for all integers n\geq1.

Exercise \PageIndex{11}\label{ex:divides-12}

Use induction to prove that 5\mid (3^{3n+1}+2^{n+1}) for all integers n\geq1.


This page titled 5.3: Divisibility is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?