Definition 4.3.1.
Let \(n, d\in \mathbb{Z}\text{.}\) Then \(n\) is divisible by \(d\) if \(n=dk\) for some \(k\in \mathbb{Z}\text{.}\)
Section 4.3 Divisibility
In this section we introduce the idea of divisibility for integers. It is important to understand that this concept involves only integers and is not the same thing as division. Divisibility is a property while division is an operation.
If \(n=dk\) for some \(k\in \mathbb{Z}\) we can also say
- \(n\) is a multiple of \(d\text{;}\)
- \(d\) is a factor of \(n\text{;}\)
- \(d\) is a divisor of \(n\text{;}\)
- \(d\) divides \(n\text{.}\)
We use the notation \(d\mid n\), read “\(d\) divides \(n\text{.}\)”
Warning: \(d\mid n\) is a relationship between two integers. It is a statement that is either true or false. It does not equal a number. It is not the same thing as a fraction. It is not an equation, but it can be translated to the equation \(n=dk\) for some integer \(k\text{.}\)
It is important to look at the special case when \(n\) or \(d\) is 0.
- \(0\mid n\) is always false.
- \(d\mid 0\) is true if \(d\neq 0\text{.}\)
- Thus, \(0\mid 0\) is false, even though, technically, one could write \(0=0\cdot k\text{.}\)
Example 4.3.2. Finding Divisors.
Find the divisors of 6.
Answer 1.
1, 2, 3, 6, -1, -2, -3, -6
Find the divisors of 5.
Answer 2.
1, 5, -1, -5
Find the divisors of 1.
Answer 3.
1, -1
If \(d\) does not divide \(n\text{,}\) then for every \(k\in \mathbb{Z}, n\neq dk\text{.}\) This can be difficult to show in general, but if \(n\) and \(d\) are specific integers, you could show \(\frac{n}{d}\) is not an integer. This is the only time a fraction can show up in proofs about divibilty.
We use the notation \(d\nmid n\) for \(d\) does not divide \(n\text{.}\)
Example 4.3.3. Determining Divisibility.
True or false: \(8\mid 24\text{.}\)
Answer 1.
True, \(24=8(3)\text{.}\)
True or false: \(8\mid 4\text{.}\)
Answer 2.
False, \(4=8(k)\) has no integer solutions since \(k=1/2\text{.}\)
True or false: \(8\mid 10\text{.}\)
Answer 3.
False, \(10=8(k)\) has no integer solutions since \(k=5/4\text{.}\)
True or false: \(8\mid -8\text{.}\)
Answer 4.
True, \(-8=8(-1)\text{.}\)
True or false: \(-2\mid 8\text{.}\)
Answer 5.
True, \(8=-2(-4)\text{.}\)
True or false: \(1\mid 4\text{.}\)
Answer 6.
True, \(4=1(4)\text{.}\)
True or false: \(8\mid 0\text{.}\)
Answer 7.
True, \(0=8(0)\text{.}\)
True or false: \(4\mid 1\text{.}\)
Answer 8.
False, \(1=4(k)\) has no integer solutions since \(k=1/4\text{.}\)
True or false: \(0\mid 8\text{.}\)
Answer 9.
False, \(8=0(k)\) has no integer solutions.
Activity 4.3.1.
Determine if the following divisibility statements are true or false, and justify your answer.
(a)
\(3\mid 10\)(b)
\(3\mid 0\)(c)
\(3\mid 36\)(d)
\(12\mid 4\)(e)
\(0\mid 4\)Now, let’s use the definition of divisibility to prove a more general theorem.
Theorem 4.3.4.
For all integers, \(a, b, c\text{,}\) if \(a\mid b\) and \(b\mid c\text{,}\) then \(a\mid c\text{.}\)
Proof.
Let \(a, b, c\in \mathbb{Z}\text{.}\) Assume \(a\mid b\) and \(b\mid c\text{.}\) Then by definition, \(b=ak\) for some \(k\in \mathbb{Z}\) and \(c=bj\) for some \(j\in \mathbb{Z}\text{.}\) Substituting the first equation into the second, \(c=(ak)j=a(kj)\text{.}\) Since \(kj\in\mathbb{Z}\text{,}\) \(a\mid c\text{.}\)
Activity 4.3.2.
Prove if 15 divides \(n\text{,}\) then 5 divides \(n\text{.}\)
Activity 4.3.3.
Prove or disprove if 6 divides \(n\text{,}\) then 12 divides \(n\text{.}\)
Activity 4.3.4.
Prove if \(d\mid n\) and \(d\mid m\text{,}\) then \(d\mid (n+m)\text{.}\)
Now that we have the concept of divisibility, we can look at some bigger mathematical theorems involving divisibility by primes.
Theorem 4.3.5.
Any integer \(n>1\) is divisible by a prime.Proof.
We will divide this proof into two cases, where \(n\) is prime and where \(n\) is composite.
Case 1: \(n\) is prime. We can see that \(n\mid n\text{.}\) Since \(\text{}\) is prime, \(n\) is divisible by a prime.
Case 2: \(n\) is composite. Then \(n=r_0s_0\) where \(1< r_0 < n\text{,}\) and \(r_0, s_0\in \mathbb{Z}\text{.}\) If \(r_0\) is prime, then \(n\) is divisible by a prime.
If \(r_0\) is not prime, then \(r_0=r_1s_1\) where \(1< r_1 < r_0\text{,}\) and \(r_1, s_1\in \mathbb{Z}\text{.}\) If \(r_1\) is prime, then \(n=r_1s_1s_0\) and \(n\) is divisible by a prime.
Similarly, if \(r_1\) is not prime, then \(r_1=r_2s_2\) where \(1< r_2 < r_1 < r_0\text{,}\) and \(r_2, s_2\in \mathbb{Z}\text{,}\) etc.
We can keep applying this process to get \(n=r_ks_k\cdots s_0\) with \(1< r_k <\cdots< r_1 < r_0\text{,}\) and \(r_k, s_k\in \mathbb{Z}\text{.}\)
If at any point \(r_k\) is prime, then we are done, as we have found a prime divisor of \(n\text{.}\) We know that there cannot be infinitely many non-prime \(r_k\) since there are only finitely many integers between 1 and \(n\text{.}\) Thus, the process must terminate with a prime divisor of \(n\text{.}\) Hence, every integer is divisible by a prime.
We now state a big theorem in discrete mathematics, but leave the proof for later. This theorem is more commonly called the Fundamental Theorem of Arthmetic.
Theorem 4.3.6. Unique Factorization Theorem.
Given any integer \(n>1\) there exists a positive integer \(k\text{,}\) distinct primes \(p_1, p_2, \ldots, p_k\text{,}\) and positive integers \(e_1, e_2, \ldots e_k\text{,}\) such that \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\text{.}\) This factorization of \(n\) into powers of primes is unique except for the order of the factors.
The decomposition into powers of primes, \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\text{,}\) is called the standard form of the prime factorization.
Definition 4.3.7.
Let \(n\) be an integer \(n\geq 1\text{.}\) Then the factorial of \(n\) is given by \(n!=(n)(n-1)(n-2)\cdots(2)(1)\text{.}\)
For example, \(5!=5(4)(3)(2)(1)=120\text{.}\)
Example 4.3.8. Prime Factorization.
Find the prime factorization of 252 in standard form.
Answer 1.
\(252=(2^2)(3^2)(7)\text{.}\)
Find the prime factorization of 17 in standard form.
Answer 2.
\(17\text{,}\) since it is prime.
Find the prime factorization of 195 in standard form.
Answer 3.
\(195=(3)(5)(13)\text{.}\)
Find the prime factorization of \(8!\) in standard form.
Answer 4.
\begin{align*}
8!=(8)(7)(6)(5)(4)(3)(2)(1)\\
&=(2^3)(7)(2\cdot 3)(5)(2^2)(3)(2)\\
&=(2^7)(3^3)(5)(7)\text{.}
\end{align*}
Activity 4.3.5.
Give the prime factorization of 600 in standard form.
Activity 4.3.6.
Give the prime factorization of \(9!\) (9 factorial). Is 10 a factor of \(9!\text{?}\) Is \(10^2\text{?}\)
Theorem 4.3.6 is more powerful than it may seem. Although you have probably found prime factorizations before, you may not have thought much about the fact that they are unique. Consider the statement \(3\mid 2^{101}\text{.}\) Is this true or false? Well, since \(2^{101}\) is a prime factorization, the only prime divisor it has is 2. Thus, \(3\mid 2^{101}\) is false. If you have the prime factorization of an integer, then you know exactly which primes (and which powers of primes) divide the integer.
Activity 4.3.7.
Determine if the following are true or false. Give a reason for your answer.
(a)
5 divides \(3^{600}\text{.}\)
(b)
6 divides \(3^{600}\text{.}\)
(c)
9 divides \(3^{600}\text{.}\)
(d)
300 divides \(3^{600}\text{.}\)
Reading Questions Check Your Understanding
1.
True.
False.
True or false: \(6\mid 24\text{.}\)
2.
True.
False.
True or false: \(1\mid 9\text{.}\)
3.
True.
False.
True or false: \(0\mid 9\text{.}\)
4.
True.
False.
True or false: \(6\mid 3\text{.}\)
5.
True.
False.
True or false: \(6\mid 6\text{.}\)
6.
True.
False.
True or false: \(6\mid -30\text{.}\)
7.
True.
False.
True or false: \(6\mid 0\text{.}\)
8.
True.
False.
True or false: \(6\mid 21\text{.}\)
9.
True.
False.
True or false: \(5\mid 3^{56}\text{.}\)
10.
True.
False.
True or false: \(6\mid 3^{10}2^{5}5^{9}\text{.}\)
11.
Give the prime factorization for \(7!\text{.}\)
12.
True.
False.
True or false: \(10\mid 7!\text{.}\)
13.
True.
- \(100=2^25^2\text{,}\) so \(7!\) would need a factor of \(5^2\text{.}\)
False.
- \(100=2^25^2\text{,}\) so \(7!\) would need a factor of \(5^2\text{.}\)
True or false: \(100\mid 7!\text{.}\)
Exercises Exercises
1.
Determine if the following statements are true or false. Justify your answer.
- \(\displaystyle 5\mid 0\)
- \(-3\) is a factor of 66
- \(\displaystyle 13\mid 73\)
2.
Let \(n\in \mathbb{Z}\text{.}\) Determine if the following statements are true or false. Justify your answer.
- 3 divides \((3n+1)(3n+2)(3n+3)\text{.}\)
- \(6n(2n+10)\) is divisible by 4.
- 100 divides \((5n)^2(8n+24).\)
3.
Show that the following statement is false: For all integers \(a\) and \(b\text{,}\) if \(3\mid (a+b)\) then \(3\mid (a-b)\text{.}\)
4.
Recall that the standard factored form of an integer is a product of powers of a prime, as in Theorem 4.3.6.
- Write \(6!\) in standard factored form.
- Write \(20!\) in standard factored form.
- Without computing the value of \((20!)^2\) determine how many zeros are at the end of this number when written in decimal form. Justify your answer.
Hint.
For (c), What prime factors correspond to zeros at the end of a number?
5.
Prove, using the definition of divisibility, for all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid b\) and \(a\mid c\) then \(a\mid (b+c)\text{.}\)
6.
Prove or disprove: The product of any two even integers is a multiple of 4.
7.
Prove or disprove: For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(ab\mid c\) then \(a\mid c\) and \(b\mid c\text{.}\)
8.
Prove or disprove: For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\mid bc\) then \(a\mid b\) or \(a\mid c\text{.}\)
9.
Prove or disprove: For all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a\) is a factor of \(c\) then \(ab\) is a factor of \(c\text{.}\)
You have attempted of activities on this page.
