Prime Numbers and Prime Factorizations

Section 8.2 Prime Numbers and Prime Factorizations

Beginning Activity Beginning Activity 1: Exploring Examples where $a$ Divides $b \cdot c$
A4 US

1.

Find at least three different examples of nonzero integers $a,$ $b,$ and $c$ such that $a ∣ (b c)$ but $a$ does not divide $b$ and $a$ does not divide $c .$ In each case, compute $gcd (a, b)$ and $gcd (a, c) .$

🔗

2.

Find at least three different examples of nonzero integers $a,$ $b,$ and $c$ such that $gcd (a, b) = 1$ and $a ∣ (b c) .$ In each example, is there any relation between the integers $a$ and $c ?$

🔗

3.

Formulate a conjecture based on your work in Exercise 1 and Exercise 2.

🔗

Beginning Activity Beginning Activity 2: Prime Factorizations
A4 US

🔗

Recall that a natural number

p

is a prime number provided that it is greater than 1 and the only natural numbers that divide

p

are 1 and

p .

A natural number other than 1 that is not a prime number is a composite number. The number 1 is neither prime nor composite. (See Activity 8 from Section 2.4.)

🔗

1.

Give examples of four natural numbers that are prime and four natural numbers that are composite.

🔗

Theorem 4.11 in Section 4.2 states that every natural number greater than 1 is either a prime number or a product of prime numbers.

🔗

When a composite number is written as a product of prime numbers, we say that we have obtained a prime factorization of that composite number. For example, since

60 = 2^{2} \cdot 3 \cdot 5,

we say that

2^{2} \cdot 3 \cdot 5

is a prime factorization of 60.

🔗

2.

Write the number 40 as a product of prime numbers by first writing $40 = 2 \cdot 20$ and then factoring 20 into a product of primes. Next, write the number 40 as a product of prime numbers by first writing $40 = 5 \cdot 8$ and then factoring 8 into a product of primes.

🔗

3.

In Exercise 2, we used two different methods to obtain a prime factorization of 40. Did these methods produce the same prime factorization or different prime factorizations? Explain.

🔗

4.

Repeat Exercise 2 and Exercise 3 with 150. First, start with $150 = 3 \cdot 50,$ and then start with $150 = 5 \cdot 30 .$

🔗

Subsection Greatest Common Divisors and Linear Combinations

🔗

In Section 8.1, we introduced the concept of the greatest common divisor of two integers. We showed how the Euclidean Algorithm can be used to find the greatest common divisor of two integers,

a

and

b,

and also showed how to use the results of the Euclidean Algorithm to write the greatest common divisor of

a

and

b

as a linear combination of

a

and

b .

🔗

In this section, we will use these results to help prove the so-called Fundamental Theorem of Arithmetic, which states that any natural number greater than 1 that is not prime can be written as product of primes in “essentially” only one way. This means that given two prime factorizations, the prime factors are exactly the same, and the only difference may be in the order in which the prime factors are written. We start with more results concerning greatest common divisors. We first prove Proposition 5.22, which was part of Activity 30 in Section 5.2 and Activity 47 in Section 8.1.

🔗

Proposition 5.22: Let a, b, and t be integers with

t \neq 0 .

t

divides

a

and

t

divides

b,

then for all integers

x

and

y,

t

divides

(a x + b y) .

🔗

Proof.

Let $a,$ $b,$ and $t$ be integers with $t \neq 0,$ and assume that $t$ divides $a$ and $t$ divides $b .$ We will prove that for all integers $x$ and $y,$ $t$ divides $(a x + b y) .$

So let $x \in Z$ and let $y \in Z .$ Since $t$ divides $a,$ there exists an integer $m$ such that $a = m t$ and since $t$ divides $b,$ there exists an integer $n$ such that $b = n t .$ Using substitution and algebra, we then see that

\begin{aligned} a x + b y & = (m t) x + (n t) y \\ = t (m x + n y) \end{aligned}

Since $(m x + n y)$ is an integer, the last equation proves that $t$ divides $a x + b y$ and this proves that for all integers $x$ and $y,$ $t$ divides $(a x + b y) .$

🔗

We now let

a, b \in Z,

not both 0, and let

d = gcd (a, b) .

Theorem 8.10 states that

d

can be written as a linear combination of

a

and

b .

Now, since

d ∣ a

and

d ∣ b,

we can use the result of Proposition 5.22 to conclude that for all

x, y \in Z,

d ∣ (a x + b y) .

This means that

d

divides every linear combination of

a

and

b .

In addition, this means that

d

must be the smallest positive number that is a linear combination of

a

and

b .

We summarize these results in Theorem 8.11.

🔗

Theorem 8.11.

Let $a, b \in Z,$ not both 0.

The greatest common divisor, $d,$ is a linear combination of $a$ and $b .$ That is, there exist integers $m$ and $n$ such that $d = a m + b n .$
The greatest common divisor, $d,$ divides every linear combination of $a$ and $b .$ That is, for all $x, y \in Z$ , $d ∣ (a x + b y) .$
The greatest common divisor, $d,$ is the smallest positive number that is a linear combination of $a$ and $b .$

🔗

Subsection Relatively Prime Integers

🔗

In Beginning Activity 1, we constructed several examples of integers

a,

b,

and

c

such that

a ∣ (b c)

but

a

does not divide

b

and

a

does not divide

c .

For each example, we observed that

gcd (a, b) \neq 1

and

gcd (a, c) \neq 1 .

🔗

We also constructed several examples where

a ∣ (b c)

and

gcd (a, b) = 1 .

In all of these cases, we noted that

a

divides

c .

Integers whose greatest common divisor is equal to 1 are given a special name.

🔗

Definition.

Two nonzero integers $a$ and $b$ are relatively prime provided that $gcd (a, b) = 1 .$

🔗

Progress Check 8.12. Relatively Prime Integers.

🔗

(a)

Construct at least three different examples where $p$ is a prime number, $a \in Z$ , and $p ∣ a .$ In each example, what is $gcd (a, p) ?$ Based on these examples, formulate a conjecture about $gcd (a, p)$ when $p ∣ a .$

Solution.

If $a, p \in Z,$ $p$ is prime, and $p$ divides $a,$ then $gcd (a, p) = p .$

🔗

(b)

Construct at least three different examples where $p$ is a prime number, $a \in Z$ , and $p$ does not divide $a .$ In each example, what is $gcd (a, p) ?$ Based on these examples, formulate a conjecture about $gcd (a, p)$ when $p$ does not divide $a .$

Solution.

If $a, p \in Z,$ $p$ is prime, and $p$ does not divide $a,$ then $gcd (a, p) = 1 .$

🔗

(c)

Give at least three different examples of integers $a$ and $b$ where $a$ is not prime, $b$ is not prime, and $gcd (a, b) = 1,$ or explain why it is not possible to construct such examples.

Solution.

Three examples are $gcd (4, 9) = 1,$ $gcd (15, 16) = 1,$ $gcd (8, 25) = 1 .$

🔗

Theorem 8.13.

Let $a$ and $b$ be nonzero integers, and let $p$ be a prime number.

If $a$ and $b$ are relatively prime, then there exist integers $m$ and $n$ such that $a m + b n = 1 .$ That is, 1 can be written as linear combination of $a$ and $b .$
If $p ∣ a,$ then $gcd (a, p) = p .$
If $p$ does not divide $a,$ then $gcd (a, p) = 1 .$

🔗

Item 1 of Theorem 8.13 is actually a corollary of Theorem 8.11. Item 2 and Item 3 could have been the conjectures you formulated in Progress Check 8.12. The proofs are included in Exercise 1.

🔗

Given nonzero integers

a

and

b,

we have seen that it is possible to use the Euclidean Algorithm to write their greatest common divisor as a linear combination of

a

and

b .

We have also seen that this can sometimes be a tedious, time-consuming process, which is why people have programmed computers to do this. Fortunately, in many proofs of number theory results, we do not actually have to construct this linear combination since simply knowing that it exists can be useful in proving results. This will be illustrated in the proof of Theorem 8.14, which is based on work in Beginning Activity 1.

🔗

Theorem 8.14.

Let $a,$ $b$ be nonzero integers and let $c$ be an integer. If $a$ and $b$ are relatively prime and $a ∣ (b c),$ then $a ∣ c .$

🔗

The explorations in Beginning Activity 1 were related to this theorem. We will first explore the forward-backward process for the proof. The goal is to prove that

a ∣ c .

A standard way to do this is to prove that there exists an integer

q

such that

\begin{matrix} (69) & c = a q . \end{matrix}

🔗

Since we are given that

a ∣ (b c),

there exists an integer

k

such that

\begin{matrix} (70) & b c = a k . \end{matrix}

🔗

It may seem tempting to divide both sides of equation (70) by

b,

but if we do so, we run into problems with the fact that the integers are not closed under division. Instead, we look at the other part of the hypothesis, which is that

a

and

b

are relatively prime. This means that

gcd (a, b) = 1 .

How can we use this? This means that

a

and

b

have no common factors except for 1. In light of equation (70) it seems reasonable that any factor of

a

must also be a factor of

c .

But how do we formalize this?

🔗

One conclusion that we can use is that since

gcd (a, b) = 1,

by Theorem 8.13, there exist integers

m

and

n

such that

\begin{matrix} (71) & a m + b n = 1 . \end{matrix}

🔗

We may consider solving equation (71) for

b

and substituting this into equation (70) The problem, again, is that in order to solve equation (71) for

b,

we need to divide by

n .

🔗

Before doing anything else, we should look at the goal in equation (69) We need to introduce

c

into equation (71) One way to do this is to multiply both sides of equation (71) by

c .

(This keeps us in the system of integers since the integers are closed under multiplication.) This gives

\begin{aligned} (a m + b n) c & = 1 \cdot c \\ (72) & a c m + b c n & = c \end{aligned}

🔗

Notice that the left side of equation (72) contains a term,

b c n,

that contains

b c .

This means that we can use equation (70) and substitute

b c = a k

in equation (72). After doing this, we can factor the left side of the equation to prove that

a ∣ c .

🔗

Progress Check 8.15. Completing the Proof of Theorem 8.14.

Write a complete proof of Theorem 8.14.

Solution.

🔗

Proof.

Let $a,$ $b,$ and $c$ be integers. Assume that $a$ and $b$ are relatively prime and $a ∣ (b c) .$ We will prove that $a$ divides $c .$

Since $a$ divides $b c,$ there exists an integer $k$ such that

\begin{matrix} (73) & b c = a k . \end{matrix}

In addition, we are assuming that $a$ and $b$ are relatively prime and hence $gcd (a, b) = 1 .$ So by Theorem 8.11, there exist integers $m$ and $n$ such that

\begin{matrix} (74) & a m + b n = 1 . \end{matrix}

We now multiply both sides of equation (74) by $c .$ This gives

\begin{aligned} (a m + b n) c & = 1 \cdot c \\ (75) & a c m + b c n & = c \end{aligned}

We can now use equation 1 to substitute $b c = a k$ in equation (75) and obtain

a c m + a k n = c .

If we now factor the left side of this last equation, we see that $a (c m + k n) = c .$ Since $(c m + k n)$ is an integer, this proves that $a$ divides $c .$ Hence, we have proven that if $a$ and $b$ are relatively prime and $a ∣ (b c),$ then $a ∣ c .$

🔗

Corollary 8.16.

Let $a, b \in Z,$ and let $p$ be a prime number. If $p ∣ (a b),$ then $p ∣ a$ or $p ∣ b .$
Let $p$ be a prime number, let $n \in N,$ and let $a_{1}, a_{2}, \dots, a_{n} \in Z .$ If $p ∣ (a_{1} a_{2} \dots a_{n}),$ then there exists a natural number $k$ with $1 \leq k \leq n$ such that $p ∣ a_{k} .$

🔗

Item 1 of Corollary 8.16 is a corollary of Theorem 8.14. Item 2 is proved using mathematical induction. The basis step is the case where

n = 1,

and Item 1 is the case where

n = 2 .

The proofs of these two results are included in Exercise 2 and Exercise 3.

🔗

Subsection Historical Note

🔗

Item 1 of Corollary 8.16 is known as Euclid's Lemma. Most people associate geometry with Euclid's Elements, but these books also contain many basic results in number theory. Many of the results that are contained in this section appeared in Euclid's Elements.

🔗

Subsection Prime Numbers and Prime Factorizations

🔗

We are now ready to prove the Fundamental Theorem of Arithmetic. The first part of this theorem was proved in Theorem 4.11 in Section 4.2. This theorem states that each natural number greater than 1 is either a prime number or is a product of prime numbers. Before we state the Fundamental Theorem of Arithmetic, we will discuss some notational conventions that will help us with the proof. We start with an example.

🔗

We will use

n = 120 .

Since

5 ∣ 120,

we can write

120 = 5 \cdot 24 .

In addition, we can factor 24 as

24 = 2 \cdot 2 \cdot 2 \cdot 3 .

So we can write

\begin{aligned} 120 & = 5 \cdot 24 \\ = 5 (2 \cdot 2 \cdot 2 \cdot 3) . \end{aligned}

🔗

This is a prime factorization of 120, but it is not the way we usually write this factorization. Most often, we will write the prime number factors in ascending order. So we write

120 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 or 120 = 2^{3} \cdot 3 \cdot 5 .

🔗

Now, let

n \in N .

To write the prime factorization of

n

with the prime factors in ascending order requires that if we write

n = p_{1} p_{2} \dots p_{r},

where

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

are prime numbers, we will have

p_{1} \leq p_{2} \leq \dots \leq p_{r} .

🔗

Theorem 8.17. The Fundamental Theorem of Arithmetic.

Each natural number greater than 1 is either a prime number or is a product of prime numbers.
Let $n \in N$ with $n > 1 .$ Assume that

$n = p_{1} p_{2} \dots p_{r} and that n = q_{1} q_{2} \dots q_{s},$

where $p_{1}, p_{2}, \dots, p_{r}$ and $q_{1}, q_{2}, \dots, q_{s}$ are primes with $p_{1} \leq p_{2} \leq \dots \leq p_{r}$ and $q_{1} \leq q_{2} \leq \dots \leq q_{s} .$ Then $r = s,$ and for each $j$ from 1 to r, $p_{j} = q_{j} .$

🔗

Proof.

The first part of this theorem was proved in Theorem 4.11. We will prove the second part of the theorem by induction on $n$ using the Second Principle of Mathematical Induction. (See Section 4.2.) For each natural number $n$ with $n > 1,$ let $P (n)$ be

If $n = p_{1} p_{2} \dots p_{r}$ and $n = q_{1} q_{2} \dots q_{s},$ where $p_{1}, p_{2}, \dots, p_{r}$ and $q_{1}, q_{2}, \dots, q_{s}$ are primes with $p_{1} \leq p_{2} \leq \dots \leq p_{r}$ and $q_{1} \leq q_{2} \leq \dots \leq q_{s},$ then $r = s,$ and for each $j$ from 1 to $r,$ $p_{j} = q_{j} .$

For the basis step, we notice that since 2 is a prime number, its only factorization is $2 = 1 \cdot 2 .$ This means that the only equation of the form $2 = p_{1} p_{2} \dots p_{r},$ where $p_{1}, p_{2}, \dots, p_{r}$ are prime numbers, is the case where $r = 1$ and $p_{1} = 2 .$ This proves that $P (2)$ is true.

For the inductive step, let $k \in N$ with $k \geq 2 .$ We will assume that $P (2), P (3), \dots, P (k)$ are true. The goal now is to prove that $P (k + 1)$ is true. To prove this, we assume that $(k + 1)$ has two prime factorizations and then prove that these prime factorizations are the same. So we assume that

$k + 1 = p_{1} p_{2} \dots p_{r}$ and that $k + 1 = q_{1} q_{2} \dots q_{s},$ where $p_{1}, p_{2}, \dots, p_{r}$ and $q_{1}, q_{2}, \dots, q_{s}$ are primes with $p_{1} \leq p_{2} \leq \dots \leq p_{r}$ and $q_{1} \leq q_{2} \leq \dots \leq q_{s} .$

We must now prove that

r = s,

and for each

j

from 1 to

r,

p_{j} = q_{j} .

We can break our proof into two cases: (1)

p_{1} \leq q_{1};

and (2)

q_{1} \leq p_{1} .

Since one of these must be true, and since the proofs will be similar, we can assume, without loss of generality, that

p_{1} \leq q_{1} .

Since $k + 1 = p_{1} p_{2} \dots p_{r},$ we know that $p_{1} ∣ (k + 1),$ and hence we may conclude that $p_{1} ∣ (q_{1} q_{2} \dots q_{s}) .$ We now use Corollary 8.16 to conclude that there exists a $j$ with $1 \leq j \leq s$ such that $p_{1} ∣ q_{j} .$ Since $p_{1}$ and $q_{j}$ are primes, we conclude that

p_{1} = q_{j} .

We have also assumed that $q_{1} \leq q_{j}$ for all $j$ and, hence, we know that $q_{1} \leq p_{1} .$ However, we have also assumed that $p_{1} \leq q_{1} .$ Hence,

p_{1} = q_{1} .

We now use this and the fact that $k + 1 = p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s}$ to conclude that

p_{2} \dots p_{r} = q_{2} \dots q_{s} .

The product in the previous equation is less than $k + 1 .$ Hence, we can apply our induction hypothesis to these factorizations and conclude that $r = s,$ and for each $j$ from 2 to $r,$ $p_{j} = q_{j} .$

This completes the proof that if $P (2), P (3), \dots, P (k)$ are true, then $P (k + 1)$ is true. Hence, by the Second Principle of Mathematical Induction, we conclude that $P (n)$ is true for all $n \in N$ with $n \geq 2 .$ This completes the proof of the theorem.

🔗

Note: We often shorten the result of the Fundamental Theorem of Arithmetic by simply saying that each natural number greater than one that is not a prime has a unique factorization as a product of primes. This simply means that if

n \in N,

n > 1,

and

n

is not prime, then no matter how we choose to factor

n

into a product of primes, we will always have the same prime factors. The only difference may be in the order in which we write the prime factors.

🔗

Subsection Further Results and Conjectures about Prime Numbers

The Number of Prime Numbers.
Prime numbers have fascinated mathematicians for centuries. For example, we can easily start writing a list of prime numbers in ascending order. Following is a list of the prime numbers less than 100.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

This list contains the first 25 prime numbers. Does this list ever stop? The question was answered in Euclid's Elements, and the result is stated in Theorem 8.18. The proof of this theorem is considered to be one of the classical proofs by contradiction.

🔗
Theorem 8.18.

There are infinitely many prime numbers.
🔗
Proof.

We will use a proof by contradiction. We assume that there are only finitely many primes, and let

$p_{1}, p_{2}, \dots, p_{m}$

be the list of all the primes. Let

$\begin{matrix} (76) & M = p_{1} p_{2} \dots p_{m} + 1 . \end{matrix}$

Notice that $M \neq 1 .$ So $M$ is either a prime number or, by the Fundamental Theorem of Arithmetic, $M$ is a product of prime numbers. In either case, $M$ has a factor that is a prime number. Since we have listed all the prime numbers, this means that there exists a natural number $j$ with $1 \leq j \leq m$ such that $p_{j} ∣ M .$ Now, we can rewrite equation (76) as follows:

$\begin{matrix} (77) & 1 = M - p_{1} p_{2} \dots p_{m} . \end{matrix}$

We have proved $p_{j} ∣ M,$ and since $p_{j}$ is one of the prime factors of $p_{1} p_{2} \dots p_{m},$ we can also conclude that $p_{j} ∣ (p_{1} p_{2} \dots p_{m}) .$ Since $p_{j}$ divides both of the terms on the right side of equation (77), we can use this equation to conclude that $p_{j}$ divides 1. This is a contradiction since a prime number is greater than 1 and cannot divide 1. Hence, our assumption that there are only finitely many primes is false, and so there must be infinitely many primes.
The Distribution of Prime Numbers.
There are infinitely many primes, but when we write a list of the prime numbers, we can see some long sequences of consecutive natural numbers that contain no prime numbers. For example, there are no prime numbers between 113 and 127. The following theorem shows that there exist arbitrarily long sequences of consecutive natural numbers containing no prime numbers. A guided proof of this theorem is included in Exercise 15.
🔗
Theorem 8.19.

For any natural number $n,$ there exist at least $n$ consecutive natural numbers that are composite numbers.

🔗

There are many unanswered questions about prime numbers, two of which will now be discussed.

The Twin Prime Conjecture.
By looking at the list of the first 25 prime numbers, we see several cases where consecutive prime numbers differ by 2. Examples are: 3 and 5; 11 and 13; 17 and 19; 29 and 31. Such pairs of prime numbers are said to be twin primes. How many twin primes exist? The answer is not known. The Twin Prime Conjecture states that there are infinitely many twin primes. As of June 25, 2010, this is still a conjecture as it has not been proved or disproved. For some interesting information on prime numbers, visit the Web site The Prime Pages ⁸ where there is a link to The Largest Known Primes Web site. According to information at this site as of June 25, 2010, the largest known twin primes are

$(65516468355 \times 2^{333333} - 1) and (65516468355 \times 2^{333333} + 1) .$

Each of these prime numbers contains 100355 digits.
Goldbach's Conjecture.
Given an even natural number, is it possible to write it as a sum of two prime numbers? For example,

$\begin{aligned} 4 & = 2 + 2 & 6 & = 3 + 3 & 8 & = 5 + 3 \\ 78 & = 37 + 41 & 90 & = 43 + 47 & 138 & = 67 + 71 \end{aligned}$

One of the most famous unsolved problems in mathematics is a conjecture made by Christian Goldbach in a letter to Leonhard Euler in 1742. The conjecture, now known as Goldbach's Conjecture, is as follows:
Every even integer greater than 2 can be expressed as the sum of two (not necessarily distinct) prime numbers.
As of June 25, 2010, it is not known if this conjecture is true or false, although most mathematicians believe it to be true.

🔗

Exercises Exercises

🔗

1.

Prove the second and third parts of Theorem 8.13.

🔗

(a)

Let $a$ be a nonzero integer, and let $p$ be a prime number. If $p ∣ a,$ then $gcd (a, p) = p .$

Hint.

Use the fact that the only natural number divisors of a prime number $p$ are 1 and $p .$

🔗

(b)

Let $a$ be a nonzero integer, and let $p$ be a prime number. If $p$ does not divide $a,$ then $gcd (a, p) = 1 .$

Hint.

Use the fact that the only natural number divisors of a prime number $p$ are 1 and $p .$

🔗

2.

Prove the first part of Corollary 8.16. Let $a, b \in Z,$ and let $p$ be a prime number. If $p ∣ (a b),$ then $p ∣ a$ or $p ∣ b .$

Hint.

Consider two cases: (1) $p ∣ a;$ and (2) $p$ does not divide $a .$

Answer.

Use cases: (1) $p$ divides $a;$ (2) $p$ does not divide $a .$ In the first case, the conclusion is automatically true. For the second case, use the fact that $gcd (p, a) = 1$ and so we can use Theorem 8.14 to conclude that $p$ divides $b .$ Another option is to write the number 1 as a linear combination of $a$ and $p$ and then multiply both sides of the equation by $b .$

🔗

3.

Use mathematical induction to prove the second part of Corollary 8.16. Let $p$ be a prime number, let $n \in N,$ and let $a_{1}, a_{2}, \dots, a_{n} \in Z .$ If $p ∣ (a_{1} a_{2} \dots a_{n}),$ then there exists a $k \in N$ with $1 \leq k \leq n$ such that $p ∣ a_{k} .$

Hint.

A hint for the inductive step: Write $p ∣ (a_{1} a_{2} \dots a_{m}) a_{m + 1} .$ Then look at two cases: (1) $p ∣ a_{m + 1};$ (2) $p$ does not divide $a_{m + 1} .$

🔗

4.

Let $a$ and $b$ be nonzero integers.

🔗

(a)

If there exist integers $x$ and $y$ such that $a x + b y = 1,$ what conclusion can be made about $gcd (a, b) ?$ Explain.

Answer.

$gcd (a, b) = 1 .$ Why?

🔗

(b)

If there exist integers $x$ and $y$ such that $a x + b y = 2,$ what conclusion can be made about $gcd (a, b) ?$ Explain.

Answer.

$gcd (a, b) = 1$ or $gcd (a, b) = 2 .$ Why?

🔗

5.

Let $a \in Z .$

🔗

(a)

What is $gcd (a, a + 1) ?$ That is, what is the greatest common divisor of two consecutive integers? Justify your conclusion. \hint Exercise 4 might be helpful.

🔗

(b)

What conclusion can be made about $gcd (a, a + 2) ?$ That is, what conclusion can be made about the greatest common divisor of two integers that differ by 2? Justify your conclusion.

🔗

6.

Let $a \in Z .$

🔗

(a)

What conclusion can be made about $gcd (a, a + 3) ?$ That is, what conclusion can be made about the greatest common divisor of two integers that differ by 3? Justify your conclusion.

🔗

(b)

What conclusion can be made about $gcd (a, a + 4) ?$ That is, what conclusion can be made about the greatest common divisor of two integers that differ by 4? Justify your conclusion.

🔗

7.

Complete the following.

🔗

(a)

Let $a = 16$ and $b = 28 .$ Determine the value of $d = gcd (a, b),$ and then determine the value of $gcd (\frac{a}{d}, \frac{b}{d}) .$

Answer.

$gcd (16, 28) = 4 .$ Also, $\frac{16}{4} = 4,$ $\frac{28}{4} = 7,$ and $gcd (4, 7) = 1 .$

🔗

(b)

Repeat Task 7.a with $a = 10$ and $b = 45 .$

Answer.

$gcd (10, 45) = 5 .$ Also, $\frac{10}{5} = 2,$ $\frac{45}{5} = 9,$ and $gcd (2, 9) = 1 .$

🔗

(c)

Let $a, b \in Z,$ not both equal to 0, and let $d = gcd (a, b) .$ Explain why $\frac{a}{d}$ and $\frac{b}{d}$ are integers. Then prove that $gcd (\frac{a}{d}, \frac{b}{d}) = 1 .$

This says that if you divide both $a$ and $b$ by their greatest common divisor, the result will be two relatively prime integers.

Hint.

Start by writing $d$ as a linear combination of $a$ and $b .$

🔗

8.

Are the following propositions true or false? Justify your conclusions.

🔗

(a)

For all integers $a, b, and c,$ if $a ∣ c$ and $b ∣ c,$ then $(a b) ∣ c .$

🔗

(b)

For all integers $a, b, and c,$ if $a ∣ c,$ $b ∣ c$ and $gcd (a, b) = 1,$ then $(a b) ∣ c .$

🔗

9.

In Exercise 17 in Section 3.5, it was proved that if $n$ is an odd integer, then $8 ∣ (n^{2} - 1) .$ (This result was also proved in Exercise 19 in Section 7.4.) Now, prove the following proposition:

If $n$ is an odd integer and 3 does not divide $n,$ then $24 ∣ (n^{2} - 1) .$

Hint.

Task 8.b of Exercise 8 can be helpful.

🔗

10.

Prove the following propositions. Use mathematical induction for Task 10.b

🔗

(a)

For all $a, b, c \in Z,$ $gcd (a, b c) = 1$ if and only if $gcd (a, b) = 1$ and $gcd (a, c) = 1 .$

🔗

(b)

Let $n \in N$ and let $a, b_{1}, b_{2}, \dots, b_{n} \in Z .$ If $gcd (a, b_{i}) = 1$ for all $i \in N$ with $1 \leq i \leq n,$ then $gcd (a, b_{1} b_{2} \dots b_{n}) = 1 .$

🔗

11.

Is the following proposition true or false? Justify your conclusion.

For all integers $a, b, and c,$ if $gcd (a, b) = 1$ and $c ∣ (a + b),$ then $gcd (a, c) = 1$ and $gcd (b, c) = 1 .$

Answer.

The statement is true. Start of a proof: If $gcd (a, b) = 1$ and $c ∣ (a + b),$ then there exist integers $x$ and $y$ such that $a x + b y = 1$ and there exists an integer $m$ such that $a + b = c m .$

🔗

12.

Is the following proposition true or false? Justify your conclusion.

If $n \in N,$ then $gcd (5 n + 2, 12 n + 5) = 1 .$

🔗

13.

Let $y \in N .$ Use the Fundamental Theorem of Arithmetic to prove that there exists an odd natural number $x$ and a nonnegative integer $k$ such that $y = 2^{k} x .$

🔗

14.

Complete the following.

🔗

(a)

Determine five different primes that are congruent to 3 modulo 4.

🔗

(b)

Prove that there are infinitely many primes that are congruent to 3 modulo 4.

🔗

15.

Let $n \in N .$

🔗

(a)

Prove that 2 divides $[(n + 1)! + 2] .$

🔗

(b)

Prove that 3 divides $[(n + 1)! + 3] .$

🔗

(c)

Prove that for each $k \in N$ with $2 \leq k \leq (n + 1),$ $k$ divides $[(n + 1)! + k] .$

🔗

(d)

Use the result of Task 15.c to prove that for each $n \in N,$ there exist at least $n$ consecutive composite natural numbers.

🔗

16.

The Twin Prime Conjecture states that there are infinitely many twin primes, but it is not known if this conjecture is true or false. The answers to the following questions, however, can be determined.

🔗

(a)

How many pairs of primes $p$ and $q$ exist where $q - p = 3 ?$ That is, how many pairs of primes are there that differ by 3? Prove that your answer is correct. (One such pair is 2 and 5.)

🔗

(b)

How many triplets of primes of the form $p,$ $p + 2,$ and $p + 4$ are there? That is, how many triplets of primes exist where each prime is 2 more than the preceding prime? Prove that your answer is correct. Notice that one such triplet is 3, 5, and 7.

Hint.

Try setting up cases using congruence modulo 3.

🔗

17.

Prove the following proposition:

Let $n \in N .$ For each $a \in Z,$ if $gcd (a, n) = 1,$ then for every $b \in Z,$ there exists an $x \in Z$ such that $a x \equiv b (\mod n) .$

Hint.

One way is to start by writing 1 as a linear combination of $a$ and $n .$

🔗

18.

Prove the following proposition:

For all natural numbers $m$ and $n,$ if $m$ and $n$ are twin primes other than the pair 3 and 5, then 36 divides $m n + 1$ and $m n + 1$ is a perfect square.

Hint.

Look at several examples of twin primes. What do you notice about the number that is between the two twin primes? Set up cases based on this observation.

🔗

Activity 48. Square Roots and Irrational Numbers.

In Chapter 3, we proved that some square roots (such as $\sqrt{2}$ and $\sqrt{3}$ ) are irrational numbers. In this activity, we will use the Fundamental Theorem of Arithmetic to prove that if a natural number is not a perfect square, then its square root is an irrational number.

🔗

(a)

Let $n$ be a natural number. Use the Fundamental Theorem of Arithmetic to explain why if $n$ is composite, then there exist distinct prime numbers $p_{1}, p_{2}, \dots, p_{r}$ and natural numbers $α_{1}, α_{2}, \dots, α_{r}$ such that

\begin{matrix} (78) & n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{r}^{α_{r}} . \end{matrix}

Using $r = 1$ and $α_{1} = 1$ for a prime number, explain why we can write any natural number greater than one in the form given in equation (78).

🔗

(b)

A natural number $b$ is a perfect square if and only if there exists a natural number $a$ such that $b = a^{2} .$ Explain why 36, 400, and 15876 are perfect squares. Then determine the prime factorization of these perfect squares. What do you notice about these prime factorizations?

🔗

(c)

Let $n$ be a natural number written in the form given in equation (78) in Task 48.a Prove that $n$ is a perfect square if and only if for each natural number $k$ with $1 \leq k \leq r,$ $α_{k}$ is even.

🔗

(d)

Prove that for all natural numbers $n,$ if $n$ is not a perfect square, then $\sqrt{n}$ is an irrational number.

Hint.

Use a proof by contradiction.

primes.utm.edu/

Section 8.2 Prime Numbers and Prime Factorizations

Beginning Activity Beginning Activity 1: Exploring Examples where a Divides b⋅c A4US

1.

2.

3.

Beginning Activity Beginning Activity 2: Prime Factorizations A4US

1.

2.

3.

4.

Subsection Greatest Common Divisors and Linear Combinations

Proof.

Theorem 8.11.

Subsection Relatively Prime Integers

Definition.

Progress Check 8.12. Relatively Prime Integers.

(a)

(b)

(c)

Theorem 8.13.

Theorem 8.14.

Progress Check 8.15. Completing the Proof of Theorem 8.14.

Proof.

Corollary 8.16.

Subsection Historical Note

Subsection Prime Numbers and Prime Factorizations

Theorem 8.17. The Fundamental Theorem of Arithmetic.

Proof.

Subsection Further Results and Conjectures about Prime Numbers

Theorem 8.18.

Proof.

Theorem 8.19.

Exercises Exercises

1.

(a)

(b)

2.

3.

4.

(a)

(b)

5.

(a)

(b)

6.

(a)

(b)

7.

(a)

(b)

(c)

8.

(a)

(b)

9.

10.

(a)

(b)

11.

12.

13.

14.

(a)

(b)

15.

(a)

(b)

(c)

(d)

16.

(a)

(b)

17.

18.

Activity 48. Square Roots and Irrational Numbers.

(a)

(b)

(c)

(d)

Beginning Activity Beginning Activity 1: Exploring Examples where $a$ Divides $b \cdot c$
A4 US

Beginning Activity Beginning Activity 2: Prime Factorizations
A4 US