19 - Prime Numbers

!Screenshot 2023-10-23 at 10.03.13 AM.png!Screenshot 2023-10-23 at 10.03.21 AM.png!Screenshot 2023-10-23 at 10.03.31 AM.png
!Screenshot 2023-10-23 at 10.03.54 AM.png
!Screenshot 2023-10-23 at 10.04.06 AM.png
!Screenshot 2023-10-23 at 10.04.28 AM.png
!Screenshot 2023-10-23 at 10.04.43 AM.png

In Class Practice

There are infinitely many prime numbers.
Let S be any finite set of prime numbers. Let

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

Then $n \geq 2$ so $n$ is divisible by some prime $q$ . Now $q ∤ 1$ , so $q ∤ (n - \prod_{p \in S})$ . This implies that $q \notin S$ . Therefore, S cannot be the set of all primes. Since no finite set of primes contains all primes, there must be infinitely many primes.

HW 19

Ben Finch

E 19.1
a) 27 = $3^{3}$
b) $3072 = 2^{10} \cdot 3$
c) 60 = $2^{2} \cdot 5 \cdot 3$

E 19.2
Let $p$ be prime and let $n \in N$ .
P(n): If $p$ divides any product of $n$ integers, then $p$ divides one of those integers.
Base cases:
P(1): If $p ∣ a$ then $p ∣ a$ for some $a \in Z$ .
P(2): If $p ∣ a_{1} a_{2}$ then $p ∣ a_{1}$ or $p ∣ a_{2}$ by Theorem 19.5.

Inductive step:
Assume $p ∣ a_{1} . . . a_{k}$ . We aim to show that $p ∣ a_{1} . . . a_{k + 1}$ . We find

a_{1} . . . a_{k + 1} = (a_{1} . . . a_{k}) a_{k + 1}

By assumption $p ∣ a_{1} . . . a_{k}$ . So by theorem 19.5, $p ∣ a_{1} . . . a_{k}$ or $p ∣ a_{k + 1}$ .

Thus by mathematical induction, P(n) is true. $◻$

E 19.3
Proof.
Let $n > 1$ and $n \in N$ . Choose $d$ to be the smallest divisor of $n$ greater than 1. Assume by way of contradiction that $d$ is prime. Then by theorem 19.3 there exist integers $a, b$ such that $d = a b$ . Then $a < d$ , $b < d$ and $a ∣ n$ and $b ∣ n$ . Thus d is not the smallest divisor of $n$ . Herein lies the contradiction. Hence $d$ is prime. $◻$

E 19.4
a)
Proof.
Let $P (p) :$ every prime number is congruent to either 1 or -1 modulo 3, $p \neq 3$ . (3 is the exception).

Consider an arbitrary prime number $p$ . Any integer $p$ can be written in one of the three cases:

$3 k$ ( $p$ is a multiple of $3$ ). If $p = 3 k$ , then $p$ is not a prime number (except for $p = 3$ ), because it can be divided by $3$ without remainder.
$3 k + 1$ ( $p$ leaves a remainder of $1$ when divided by $3$ ). If $p = 3 k + 1$ , then $p$ is congruent to $1$ modulo $3$ .
$3 k + 2$ ( $p$ leaves a remainder of $2$ when divided by $3$ ). This is equivalent to $3 k - 1$ if modulated by 3. If $p = 3 k - 1$ , then $p$ is congruent to $- 1$ modulo $3$ .

for some integer $k$ .

Hence, with only one exception ( $p = 3$ ), every prime number is congruent to either $1$ or $- 1$ modulo $3$ . $◻$

b)
Proof.

Base Case:

When $n = 1$ , we have one number $a_{1}$ . Since we assume each $a_{i} \equiv 1 \mod 3$ , we know that $a_{1} \equiv 1 \mod 3$ .

Inductive Step:

Now, we assume that the proposition is true for some $n = k$ , or in other words $a_{1} a_{2} . . . a_{k} \equiv 1 (m o d 3)$ .

We want to prove that the proposition is true for $n = k + 1$ .

Consider the product of $k + 1$ numbers, $a_{1} a_{2} . . . a_{k + 1}$ . We know from our inductive hypothesis that the product $a_{1} a_{2} . . . a_{k} \equiv 1 \mod 3$ .

We find:

$a_{1} a_{2} . . . a_{k} \cdot a_{k + 1} \equiv 1 \cdot a_{k + 1} (m o d 3)$

By the inductive assumption, we know that $a_{k + 1} \equiv 1 \mod 3$ , so we can replace $a_{k + 1}$ with 1 in the above equation:

$1 \cdot a_{k + 1} \equiv 1 \cdot 1 \mod 3$

Therefore, $a_{1} a_{2} . . . a_{k + 1} \equiv 1 \mod 3$ .

Hence, by mathematical induction, the proposition is true for all $n \in N$ . $◻$

c)
Proof.
Let $n \in N$ and $n \equiv - 1 \mod 3$ . We aim to prove that $n$ is divisible by some prime $p$ such that $p \equiv - 1 \mod 3$ . Assume by way of contradiction that $n$ does not have some prime factor $p$ such that $p \equiv - 1 \mod 3$ . From part a, we know that every prime factor is either 1 or -1 modulo 3, or $p = 3$ . We can consider two cases for the prime factors of $n$ .

Suppose all prime factors of $n$ are congruent to 1 modulo 3. If all prime factors are of the form $3 k + 1$ for some integer $k$ , then their product will also be of the form $3 m + 1$ for some integer $m$ , per part b. However, $n \equiv - 1 \mod 3$ , which contradicts this result.
Suppose one of the prime factors is $p = 3$ . Then $n$ is a multiple of 3 or $n = 3$ . If $n$ is a multiple of 3, then $n$ is not prime, which is a contradiction. If $n = 3$ , then $n ≢ - 1 \mod 3$ , which is a contradiction.

Thus in all cases, there is a contradiction. Hence $n$ is divisible by some prime $p$ such that $p \equiv - 1 \mod 3$ . $◻$

d)
$P r o o f .$ Let $S$ be any finite set of prime numbers. Let

n = - 1 + 3 (p_{1} p_{2} . . . p_{n})

Then $n \geq 2$ so $n$ is divisible by some prime $q$ 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 that are congruent to $- 1 \mod 3$ .

E 19.5
a)
Proof.
Let $P (p) :$ every prime number is congruent to either 1 or -1 modulo 4, $p \neq 2$ . (2 is the exception).

Consider an arbitrary prime number $p$ . Any integer $p$ can be written in one of the four cases:

$4 k$ ( $p$ is a multiple of $4$ ). If $p = 4 k$ , then $p$ is not a prime number (except for $p = 2$ ), because it can be divided by $4$ without remainder.
$4 k + 1$ ( $p$ leaves a remainder of $1$ when divided by $4$ ). If $p = 4 k + 1$ , then $p$ is congruent to $1$ modulo $4$ .
$4 k + 2$ ( $p$ leaves a remainder of $2$ when divided by $4$ ). If $p = 4 k + 2$ , then $p$ is not a prime number because it can be divided by $2$ without remainder.
$4 k + 3$ ( $p$ leaves a remainder of $3$ when divided by $4$ ). This is equivalent to $4 k - 1$ if modulated by 4. If $p = 4 k - 1$ , then $p$ is congruent to $- 1$ modulo $4$ .

for some integer $k$ .

Hence, with only one exception ( $p = 2$ ), every prime number is congruent to either $1$ or $- 1$ modulo $4$ . $◻$

b)
Proof.

Base Case:

When $n = 1$ , we have one number $a_{1}$ . Since we assume each $a_{i} \equiv 1 \mod 4$ , we know that $a_{1} \equiv 1 \mod 4$ .

Inductive Step:

Now, we assume that the proposition is true for some $n = k$ , or in other words $a_{1} a_{2} . . . a_{k} \equiv 1 (m o d 4)$ .

We want to prove that the proposition is true for $n = k + 1$ .

Consider the product of $k + 1$ numbers, $a_{1} a_{2} . . . a_{k + 1}$ . We know from our inductive hypothesis that the product $a_{1} a_{2} . . . a_{k} \equiv 1 \mod 4$ .

We find:

$a_{1} a_{2} . . . a_{k} \cdot a_{k + 1} \equiv 1 \cdot a_{k + 1} (m o d 4)$

By the inductive assumption, we know that $a_{k + 1} \equiv 1 \mod 4$ , so we can replace $a_{k + 1}$ with 1 in the above equation:

$1 \cdot a_{k + 1} \equiv 1 \cdot 1 \mod 4$

Therefore, $a_{1} a_{2} . . . a_{k + 1} \equiv 1 \mod 4$ .

Hence, by mathematical induction, the proposition is true for all $n \in N$ . $◻$

c)
Proof.
Let $n \in N$ and $n \equiv - 1 \mod 4$ . We aim to prove that $n$ is divisible by some prime $p$ such that $p \equiv - 1 \mod 4$ . Assume by way of contradiction that $n$ does not have some prime factor $p$ such that $p \equiv - 1 \mod 4$ . From part a, we know that every prime factor is either 1 or -1 modulo 4, or $p = 2$ . We can consider two cases for the prime factors of $n$ .

Suppose all prime factors of $n$ are congruent to 1 modulo 4. If all prime factors are of the form $4 k + 1$ for some integer $k$ , then their product will also be of the form $4 m + 1$ for some integer $m$ , per part b. However, $n \equiv - 1 \mod 4$ , which contradicts this result.
Suppose one of the prime factors is $p = 2$ . Then $n$ is a multiple of 2 or $n = 2$ . If $n$ is a multiple of 2, then $n$ is not prime, which is a contradiction. If $n = 2$ , then $n ≢ - 1 \mod 4$ , which is a contradiction.

Thus in all cases, there is a contradiction. Hence $n$ is divisible by some prime $p$ such that $p \equiv - 1 \mod 4$ . $◻$

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

n = - 1 + 4 (p_{1} p_{2} . . . p_{n})