# 5.3: Divisibility

- Page ID
- 8409

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

- \(a\)
\(b\),*divides* - \(a\) is a
of \(b\),*divisor* - \(a\) is a
of \(b\),*factor* - \(b\) is a
of \(a\), and*multiple* - \(b\) is
\(a\).*divisible by*

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 \[a \mid b \qquad \mbox{[pronounced as "\(a\) divides \(b\)'']} \nonumber\] Do not use a forward slash \(/\) or a backward slash \(\backslash\) in the notation. To say that \(a\) does not divide \(b\), we add a slash across the vertical bar, as in

\[a \nmid b \qquad \mbox{[pronounced as "$a$ does not divide $b$'']} \nonumber\] Do not confuse the notation \(a\mid b\) with \(\frac{a}{b}\). The notation \(\frac{a}{b}\) 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, \(\frac{11}{4}=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:

\(a\mid b\;\Leftrightarrow\;b=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 \(a\neq0\). In addition, \(q\) must be an integer. For instance, \(3 = 2\cdot\frac{3}{2}\), but it is certainly absurd to say that 2 divides 3.

Example \(\PageIndex{1}\label{eg:divides-01}\)

Since \(14=(-2)\cdot(-7)\), it is clear that \(-2\mid 14\).

hands-on exercise \(\PageIndex{1}\label{he:divides-01}\)

Verify that \[5 \mid 35, \quad 8\nmid 35, \quad 25\nmid 35, \quad 7 \mid 14, \quad 2 \mid -14, \quad\mbox{and}\quad 14\mid 14, \nonumber\] by finding the quotient \(q\) and the remainder \(r\) such that \(b=aq+r\), and \(r=0\) if \(a\mid b\).

Example \(\PageIndex{2}\label{eg:divides-02}\)

An integer is ** even** if and only if it is divisible by 2, and it is

**if and only if it is not divisible by 2.**

*odd*hands-on exercise \(\PageIndex{2}\label{he:divides-02}\)

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

- If \(n\) is even, then \(n=\rule{1cm}{0.4pt}\) for some integer \(\rule{1cm}{0.4pt}\).
- If \(n\) is odd, then \(n=\rule{1cm}{0.4pt}\) for \(\rule{1cm}{0.4pt}\).

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

hands-on exercise \(\PageIndex{3}\label{he:divides-03}\)

Complete the following sentence:

- If \(n\) is not divisible by 3, then \(n=\rule{1cm}{0.4pt}\,\), or \(n=\rule{1cm}{0.4pt}\,\), for some integer \(\rule{1cm}{0.4pt}\) .

Compare this to the \(\text{div}\) and \(\bmod\) operations. What are the possible values of \(n\bmod3\)?

Example \(\PageIndex{3}\label{eg:divides-03}\)

Given any integer \(a\neq 0\), we always have \(a\mid 0\) because \(0 = a\cdot 0\). In particular, 0 is divisible by 2, hence, it is considered an even integer.

Example \(\PageIndex{4}\label{eg:divides-04}\)

Similarly, \(\pm1\) and \(\pm 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

**of \(b\).**

*nontrivial divisor*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

- If \(a\mid b\), then \(a\mid xb\) for any integer \(x\).
- If \(a\mid b\) and \(b\mid c\), then \(a\mid c\). (This is called the
of divisibility.)*transitive property* - 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
of \(b\) and \(c\).)*linear combination* - If \(b\neq 0\) and \(a\mid b\) and \(b\mid a\), then \(a = \pm b\).
- 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, \nonumber\] 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'. \nonumber\] 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), \nonumber\]

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 5 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 5?

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 Problem 7 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\).