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 a≠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∣b[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
a∤b[pronounced as "a does not divide b''] Do not confuse the notation a∣b 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:
a∣b⇔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≠0. In addition, q must be an integer. For instance, 3=2⋅32, but it is certainly absurd to say that 2 divides 3.
Example 5.3.1
Since 14=(−2)⋅(−7), it is clear that −2∣14.
hands-on exercise 5.3.1
Verify that 5∣35,8∤35,25∤35,7∣14,2∣−14,and14∣14, by finding the quotient q and the remainder r such that b=aq+r, and r=0 if a∣b.
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 a≠0, we always have a∣0 because 0=a⋅0. 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
- 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: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.