$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.3: Divisibility

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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$$ 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 $a \mid b \qquad \mbox{[pronounced as "$$a$$ divides $$b$$'']}$ 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'']}$ 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,$ 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 odd if and only if it is not divisible by 2.

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=\bline{0.5in}$$ for some integer  .

• If $$n$$ is odd, then $$n=\bline{0.5in}$$ for  .

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=\bline{0.5in}\,$$, or $$n=\bline{0.5in}\,$$, for some integer  .

Compare this to the $$\bdiv$$ 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 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$$.