5.3: Divisibility

Last updated
Save as PDF

Page ID: 8409

$kwong.jpg$
Contributed by Harris Kwong
Professors (Mathematics) at State University of New York at Fredonia
Publisher: OpenSUNY

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

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$'']} \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 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=\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 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

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 transitive property of divisibility.)
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$.)
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$.