Exam 2 Review Theorems

Theorem 18.13
Let $a, b, c \in Z$ . If $a | b c$ and $G C D (a, b) = 1$ , then $a | c$ .

Proof. Let $a, b, c \in Z$ . Assume that $a ∣ b c$ and $G C D (a, b) = 1$ . Then $b c = a k$ for some $k \in Z$ . Also for some $x, y \in Z$ we have $a x + b y = 1$ . Multiplying this equation by $c$ we get:

\begin{aligned} c (a x + b y) & = c a x + c b y \\ = a c (x) + b c (y) \\ = a c (x) + a k (y) \\ = a (c x + k y) \end{aligned}

Hence since $c x + k y \in Z$ , we see that $a ∣ c$ .

Theorem 19.14
There are infinitely many prime numbers.

Proof. Let $S$ be any finite set of prime numbers. Let

n = 1 + \prod_{p \in S} p

Then $n > 2$ , so $n$ is divisible by some prime $q$ since by Theorem 19.7. Using the division algorithm to divide $n$ by any prime $p \in S$ leaves a remainder of 1, so no prime in $S$ divides $N$ . Hence $q$ must be a prime that is not in $S$ . Therefore $S$ cannot be the set of all primes.

Since no finite set of primes consists of all the primes, there must be infinitely many primes. $◻$