5.3: Divisibility
 Page ID
 8409
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\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 floatingpoint (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:divides01}\)
Since \(14=(2)\cdot(7)\), it is clear that \(2\mid 14\).
handson exercise \(\PageIndex{1}\label{he:divides01}\)
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:divides02}\)
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.
handson exercise \(\PageIndex{2}\label{he:divides02}\)
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.
handson exercise \(\PageIndex{3}\label{he:divides03}\)
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:divides03}\)
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:divides04}\)
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:divides05}\)
It is clear that 12 divides 132 properly, and 2 divides \(14\) properly as well. The integer 11 has no proper divisor.
handson exercise \(\PageIndex{4}\label{he:divides04}\)
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:divides06}\)
The integers \(2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\,\) are primes.
handson exercise \(\PageIndex{5}\label{he:divides07}\)
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,\] 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:divides07}\)
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\).
handson exercise \(\PageIndex{6}\label{he:divides06}\)
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:divides01}\)
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:divides02}\)
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:divides03}\)
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:divides04}\)
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:divides05}\)
Prove that if \(n\) is an odd integer, then \(n^21\) is divisible by 4.
Exercise \(\PageIndex{6}\label{ex:divides06}\)
Use the result from Problem [ex:divides05] 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:divides05]?
Exercise \(\PageIndex{7}\label{ex:divides07}\)
Prove that the square of any integer is of the form \(3k\) or \(3k+1\).
Exercise \(\PageIndex{8}\label{ex:divides08}\)
Use Problem [ex:divides07] to prove that \(3m^21\) is not a perfect square for any integer \(m\).
Exercise \(\PageIndex{9}\label{ex:divides09}\)
Use induction to prove that \(3\mid (2^{2n}1)\) for all integers \(n\geq1\).
Exercise \(\PageIndex{10}\label{ex:divides10}\)
Use induction to prove that \(8\mid (5^{2n}+7)\) for all integers \(n\geq1\).
Exercise \(\PageIndex{11}\label{ex:divides11}\)
Use induction to prove that \(5\mid (n^5n)\) for all integers \(n\geq1\).
Exercise \(\PageIndex{11}\label{ex:divides12}\)
Use induction to prove that \(5\mid (3^{3n+1}+2^{n+1})\) for all integers \(n\geq1\).