Week 3 - Day 1: Primes and Infinitely Many Primes

This session addresses common homework mistakes, delves into prime numbers and their properties, explores the Fundamental Theorem of Arithmetic, and introduces Euclid’s theorem on the infinitude of primes. We will also look at various theorems involving primes and composites.

Homework Mistake: Squaring Integers

A common mistake in HW 1 was proving that \( a^2 = 3k \) or \( a^2 = 3k + 1 \). Let’s revisit this to clarify the correct proof structure.

Question: Consecutive Composites

Can you think of 4 consecutive composite numbers? The answer is:

24, 25, 26, 27

Divisibility Lemma (Without Proof)

Lemma: For all integers \( a, b \in \mathbb{Z} \), if neither \( a \) nor \( b \) is zero, then:

\[ a \mid b \text{ and } b \mid a \Leftrightarrow a = \pm b \quad \text{or equivalently,} \quad |a| = |b|. \]

Three Equivalent Conditions for Primeness

Let \( p \in \mathbb{Z}, p \neq 0, \pm 1 \). The following three conditions are equivalent for a number \( p \) to be prime:

  1. Definition: For all \( d \in \mathbb{Z} \), \( d \mid p \Rightarrow d = \pm 1 \) or \( d = \pm p \).
  2. Theorem 1.5 (From last session): For all \( a, b \in \mathbb{Z} \), \( p \mid ab \Rightarrow p \mid a \) or \( p \mid b \).
  3. For all \( a \in \mathbb{Z} \), \( p \mid a \) or \( (p, a) = 1 \).

Proof: \( ii \Rightarrow i \)

Assume that for all \( a, b \in \mathbb{Z} \), if \( p \mid ab \), then \( p \mid a \) or \( p \mid b \). Let \( d \in \mathbb{Z} \), and assume \( d \mid p \). Our goal is to show that \( d = \pm 1 \) or \( d = \pm p \).

By definition, \( p = dk \) for some \( k \in \mathbb{Z} \). Since \( p = dk \), we know that \( p \mid dk \). By our assumption, this implies that \( p \mid d \) or \( p \mid k \).

  • Case 1: If \( p \mid d \), then since \( d \mid p \), by the divisibility lemma, it must be that \( d = \pm p \), as desired.
  • Case 2: If \( p \mid k \), then since \( p = dk \), we know \( k \mid p \), meaning \( p = \pm k \). This gives us \( \pm k = dk \), and since \( k \neq 0 \), we conclude \( d = \pm 1 \), as desired.

Thus, we have proved that \( d = \pm 1 \) or \( d = \pm p \). \( \blacksquare \)

Theorem 1.7: The Fundamental Theorem of Arithmetic

Statement: Every integer \( n \), except for 0 and \( \pm 1 \), can be expressed as a product of primes. This part of the theorem establishes the existence of prime factorizations (without addressing uniqueness).

Corollary: Divisibility by a Prime

As a corollary to the Fundamental Theorem of Arithmetic, we conclude that every integer, except for 0 and \( \pm 1 \), is divisible by a prime number.

Proof of Theorem 1.7 (Existence of Prime Factorizations)

We will prove the existence of prime factorizations for positive integers using complete induction on \( n \). This proof shows that every integer \( n \geq 2 \) can be written as a product of primes.

Base Case: \( n = 2 \)

The integer 2 is prime, and it can be written as a product of one prime: itself.

Induction Step

Now, let \( n \geq 2 \) and assume the Induction Hypothesis (IH): Every integer between 2 and \( n - 1 \) (inclusive) can be expressed as a product of primes.

The integer \( n \) is either prime or not.

Hence, \( n = ab = p_1 \cdots p_r q_1 \cdots q_s \), which is a product of primes. This completes the induction step, so by the Principle of Mathematical Induction, every integer \( n \geq 2 \) can be expressed as a product of primes. \( \blacksquare \)

Euclid’s Theorem: Infinitely Many Primes

Theorem: There are infinitely many prime numbers. Euclid’s classic proof demonstrates this by contradiction.

Proof (By Way of Contradiction)

Suppose, for the sake of contradiction, that there are only finitely many primes, denoted by:

\[ p_1, p_2, p_3, \dots, p_k. \]

Construct the integer \( A = p_1 p_2 \cdots p_k + 1 \). Notice that:

\[ A = p_1 (p_2 \cdots p_k) + 1. \]

By the Division Algorithm, the remainder when dividing \( A \) by \( p_1 \) is 1, so \( A \) is not divisible by \( p_1 \). Similarly, \( A \) is not divisible by \( p_2, \dots, p_k \), meaning that \( A \) is not divisible by any of the primes. But by the corollary to the Fundamental Theorem of Arithmetic, \( A \) must be divisible by a prime number, leading to a contradiction. Therefore, there are infinitely many primes. \( \blacksquare \)

Example: Constructing \( A \)

For example, if the primes were \( 2, 3, 5, 7, 11, 13 \), then:

\[ A = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30,031. \]

Since \( A = 30,031 \) is not divisible by any of these primes, this contradicts the assumption that these were all the primes.

Theorem: Consecutive Composite Numbers

Theorem: For every positive integer \( n \), there exist \( n \) consecutive composite numbers.

Proof

Consider the factorial \( (n+1)! \), which is the product of all integers from 1 to \( n+1 \):

\[ (n+1)! = (n+1)(n)(n-1)\cdots (3)(2)(1). \]

Notice that \( (n+1)! \) is divisible by all integers from 2 to \( n+1 \). Now, consider the sequence of numbers:

\[ 2 + (n+1)!, 3 + (n+1)!, 4 + (n+1)!, \dots, (n+1) + (n+1)!. \]

Each number in this sequence is divisible by some integer between 2 and \( n+1 \). For example:

Since each of these numbers has a nontrivial divisor, they are all composite. This shows that there are \( n \) consecutive composite numbers. \( \blacksquare \)

Example: \( n = 4 \)

When \( n = 4 \), we compute:

\[ 2 + 5! = 122, \quad 3 + 5! = 123, \quad 4 + 5! = 124, \quad 5 + 5! = 125. \]

The numbers \( 122, 123, 124, 125 \) are all composite, as expected.

Twin Prime Conjecture

The Twin Prime Conjecture (still open since 1846) posits that there are infinitely many pairs of twin primes, i.e., primes that differ by 2.

Example: Twin Primes