Divisibility

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.

🔗

Definition 4.3.1.

Let

n, d \in Z .

Then

n

is divisible by

d

n = d k

for some

k \in Z .

🔗

n = d k

for some

k \in Z

we can also say

🔗

$n$ is a multiple of $d;$
$d$ is a factor of $n;$
$d$ is a divisor of $n;$
$d$ divides $n .$

🔗

We use the notation

d ∣ n

, read “

d

divides

n .

”

🔗

Warning:

d ∣ 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 = d k

for some integer

k .

🔗

It is important to look at the special case when

n

d

is 0.

🔗

$0 ∣ n$ is always false.
$d ∣ 0$ is true if $d \neq 0 .$
Thus, $0 ∣ 0$ is false, even though, technically, one could write $0 = 0 \cdot k .$

🔗

Example 4.3.2. Finding Divisors.

Find the divisors of 6.

Answer 1.

Find the divisors of 5.

Answer 2.

Find the divisors of 1.

Answer 3.

d

does not divide

n,

then for every

k \in Z, n \neq d k .

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 ∤ n

for

d

does not divide

n .

🔗

Example 4.3.3. Determining Divisibility.

True or false:

8 ∣ 24 .

Answer 1.

24 = 8 (3) .

True or false:

8 ∣ 4 .

Answer 2.

4 = 8 (k)

k = 1 / 2 .

True or false:

8 ∣ 10 .

Answer 3.

10 = 8 (k)

k = 5 / 4 .

True or false:

8 ∣ - 8 .

Answer 4.

- 8 = 8 (- 1) .

True or false:

- 2 ∣ 8 .

Answer 5.

8 = - 2 (- 4) .

True or false:

1 ∣ 4 .

Answer 6.

4 = 1 (4) .

True or false:

8 ∣ 0 .

Answer 7.

0 = 8 (0) .

True or false:

4 ∣ 1 .

Answer 8.

1 = 4 (k)

k = 1 / 4 .

True or false:

0 ∣ 8 .

Answer 9.

8 = 0 (k)

Activity 4.3.1.

Determine if the following divisibility statements are true or false, and justify your answer.

🔗

(a)

3 ∣ 10

🔗

(b)

3 ∣ 0

🔗

(c)

3 ∣ 36

🔗

(d)

12 ∣ 4

🔗

(e)

0 ∣ 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,

a ∣ b

and

b ∣ c,

then

a ∣ c .

🔗

Proof.

Let

a, b, c \in Z .

Assume

a ∣ b

and

b ∣ c .

Then by definition,

b = a k

for some

k \in Z

and

c = b j

for some

j \in Z .

Substituting the first equation into the second,

c = (a k) j = a (k j) .

Since

k j \in Z,

a ∣ c .

Activity 4.3.2.

Prove if 15 divides

n,

then 5 divides

n .

🔗

Activity 4.3.3.

Prove or disprove if 6 divides

n,

then 12 divides

n .

🔗

Activity 4.3.4.

Prove if

d ∣ n

and

d ∣ m,

then

d ∣ (n + m) .

🔗

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 ∣ n .

Since

is prime,

n

is divisible by a prime.

Case 2:

n

is composite. Then

n = r_{0} s_{0}

where

1 < r_{0} < n,

and

r_{0}, s_{0} \in Z .

r_{0}

is prime, then

n

is divisible by a prime.

r_{0}

is not prime, then

r_{0} = r_{1} s_{1}

where

1 < r_{1} < r_{0},

and

r_{1}, s_{1} \in Z .

r_{1}

is prime, then

n = r_{1} s_{1} s_{0}

and

n

is divisible by a prime.

Similarly, if

r_{1}

is not prime, then

r_{1} = r_{2} s_{2}

where

1 < r_{2} < r_{1} < r_{0},

and

r_{2}, s_{2} \in Z,

etc.

We can keep applying this process to get

n = r_{k} s_{k} \dots s_{0}

with

1 < r_{k} < \dots < r_{1} < r_{0},

and

r_{k}, s_{k} \in Z .

If at any point

r_{k}

is prime, then we are done, as we have found a prime divisor of

n .

We know that there cannot be infinitely many non-prime

r_{k}

since there are only finitely many integers between 1 and

n .

Thus, the process must terminate with a prime divisor of

n .

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,

distinct primes

p_{1}, p_{2}, \dots, p_{k},

and positive integers

e_{1}, e_{2}, \dots e_{k},

such that

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}} .

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}} \dots p_{k}^{e_{k}},

is called the standard form of the prime factorization.

🔗

Definition 4.3.7.

Let

n

be an integer

n \geq 1 .

Then the factorial of

n

is given by

n! = (n) (n - 1) (n - 2) \dots (2) (1) .

🔗

For example,

5! = 5 (4) (3) (2) (1) = 120 .

🔗

Example 4.3.8. Prime Factorization.

Find the prime factorization of 252 in standard form.

Answer 1.

252 = (2^{2}) (3^{2}) (7) .

Find the prime factorization of 17 in standard form.

Answer 2.

17,

Find the prime factorization of 195 in standard form.

Answer 3.

195 = (3) (5) (13) .

Find the prime factorization of

8!

in standard form.

Answer 4.

\begin{aligned} 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) . \end{aligned}

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! ?

10^{2} ?

🔗

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 ∣ 2^{101} .

Is this true or false? Well, since

2^{101}

is a prime factorization, the only prime divisor it has is 2. Thus,

3 ∣ 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} .

🔗

(b)

6 divides

3^{600} .

🔗

(c)

9 divides

3^{600} .

🔗

(d)

300 divides

3^{600} .

🔗

Reading Questions Check Your Understanding

1.

True or false:

6 ∣ 24 .

🔗

True.
False.

🔗

2.

True or false:

1 ∣ 9 .

🔗

True.
False.

🔗

3.

True or false:

0 ∣ 9 .

🔗

True.
False.

🔗

4.

True or false:

6 ∣ 3 .

🔗

True.
False.

🔗

5.

True or false:

6 ∣ 6 .

🔗

True.
False.

🔗

6.

True or false:

6 ∣ - 30 .

🔗

True.
False.

🔗

7.

True or false:

6 ∣ 0 .

🔗

True.
False.

🔗

8.

True or false:

6 ∣ 21 .

🔗

True.
False.

🔗

9.

True or false:

5 ∣ 3^{56} .

🔗

True.
False.

🔗

10.

True or false:

6 ∣ 3^{10} 2^{5} 5^{9} .

🔗

True.
False.

🔗

11.

Give the prime factorization for

7! .

🔗

12.

True or false:

10 ∣ 7! .

🔗

True.
False.

🔗

13.

True or false:

100 ∣ 7! .

🔗

True.
$100 = 2^{2} 5^{2},$ so $7!$ would need a factor of $5^{2} .$
False.
$100 = 2^{2} 5^{2},$ so $7!$ would need a factor of $5^{2} .$

🔗

Exercises Exercises

1.

Determine if the following statements are true or false. Justify your answer.

🔗

$5 ∣ 0$
$- 3$ is a factor of 66
$13 ∣ 73$

🔗

2.

Let

n \in Z .

Determine if the following statements are true or false. Justify your answer.

🔗

3 divides $(3 n + 1) (3 n + 2) (3 n + 3) .$
$6 n (2 n + 10)$ is divisible by 4.
100 divides $(5 n)^{2} (8 n + 24) .$

🔗

3.

Show that the following statement is false: For all integers

a

and

b,

3 ∣ (a + b)

then

3 ∣ (a - b) .

🔗

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,

b,

and

c,

a ∣ b

and

a ∣ c

then

a ∣ (b + c) .

🔗

6.

Prove or disprove: The product of any two even integers is a multiple of 4.

🔗

7.

Prove or disprove: For all integers

a,

b,

and

c,

a b ∣ c

then

a ∣ c

and

b ∣ c .

🔗

8.

Prove or disprove: For all integers

a,

b,

and

c,

a ∣ b c

then

a ∣ b

a ∣ c .

🔗

9.

Prove or disprove: For all integers

a,

b,

and

c,

a

is a factor of

c

then

a b

is a factor of

c .

🔗

You have attempted 1 of 14 activities on this page.

🔗

Prev Top Next