Week 2 - Day 3: Prime Numbers and the Fundamental Theorem of Arithmetic

This session introduces and develops the concept of prime numbers, explores properties of GCDs involving primes, and establishes the Fundamental Theorem of Arithmetic. We also look into prime factorizations and delve into properties related to factorization and divisibility.

Prime Numbers and Irreducibility

Definition: Let \( p \in \mathbb{Z} \), \( p \neq 0, \pm 1 \). Then \( p \) is called prime if for all \( d \in \mathbb{Z} \), whenever \( d \mid p \), it must be that \( d = \pm 1 \) or \( d = \pm p \). This means that a prime number has no divisors other than 1 and itself (and their negatives).

It is important to note that, in more advanced abstract algebra, this definition corresponds to irreducibility rather than primality. However, for now, we will work with this classical definition.

Clarification on Notation: \(\pm\)

The expression \( \pm 2 \) can cause confusion. It should be interpreted as meaning "either 2 or -2" rather than a single value that covers both cases. For example:

and similarly for other values. In general, when you encounter \( X = \pm 2 \), it should be read as "X equals either 2 or -2."

Examples of GCD with 3

Let’s explore some examples using the number 3 to illustrate how the greatest common divisor behaves:

• \((3, 1) = 1\)
• \((3, 2) = 1\)
• \((3, 3) = 3\)
• \((3, 4) = 1\)
• \((3, 5) = 1\)
• \((3, 6) = 3\)
• \((3, 7) = 1\)
• \((3, 8) = 1\)

Notice the pattern: If 3 divides the second number (e.g., \( (3, 6) \)), the GCD is 3; otherwise, the GCD is 1. This pattern holds because 3 is prime.

Lemma: Prime GCDs

Lemma: If \( p \) is prime, then for any integer \( a \in \mathbb{Z} \), the greatest common divisor \((p, a)\) is either 1 or \( |p| \). This is a fundamental result about primes and their divisors.

Proof (for positive primes)

Let \( p \in \mathbb{Z}^+ \) and assume \( p \) is prime. Let \( a \in \mathbb{Z} \), and set \( d = (p, a) \) to be their GCD. Our goal is to show that \( d = 1 \) or \( d = p \).

Since \( d \) is a GCD, it must divide both \( p \) and \( a \), meaning \( d \mid p \) and \( d \mid a \). Since \( p \) is prime, the definition of primality tells us that \( d = \pm 1 \) or \( d = \pm p \). Additionally, since the GCD is always non-negative, we conclude that \( d = 1 \) or \( d = p \), which completes the proof. \( \blacksquare \)

Theorem: Equivalent Condition for Primeness

Theorem: Let \( p \in \mathbb{Z} \), \( p \neq 0, \pm 1 \). Then:

This theorem characterizes primes as numbers whose divisibility impacts the factors of a product. It’s crucial in understanding the structure of primes and their behavior in arithmetic.

Proof (One Direction: \( \Rightarrow \))

We will prove the forward direction, assuming \( p \) is prime and \( p > 0 \) to simplify the notation. Let \( a, b \in \mathbb{Z} \), and assume that \( p \mid ab \). Our goal is to show that \( p \mid a \) or \( p \mid b \).

Idea: We will use the fact that \( d = (p, a) \) is either 1 or \( p \), based on the Lemma about prime GCDs.

• Case 1: \( d = 1 \): In this case, we have \( (p, a) = 1 \), and we know that \( p \mid ab \). By Theorem 1.4, which we proved earlier, this implies that \( p \mid b \), as desired.
• Case 2: \( d = p \): Since \( d = p \), it follows that \( p \mid a \), as desired.

This completes the proof for the forward direction. \( \blacksquare \)

The Zero Factor Property (ZFP) in \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}\)

The Zero Factor Property (ZFP) states that for all \( a, b \in \mathbb{Z} \), if \( ab = 0 \), then \( a = 0 \) or \( b = 0 \). This property holds in the integers, rationals, reals, and complex numbers and is fundamental to solving equations that involve products.

Example: Solving a Quadratic Equation

Let’s solve the quadratic equation \( X^2 = 5X - 6 \). First, rewrite it as:

Next, factor the left-hand side:

By the Zero Factor Property, we conclude that \( X - 3 = 0 \) or \( X - 2 = 0 \), leading to the solutions \( X = 3 \) or \( X = 2 \).

Prime and Zero Factor Property (ZFP)

Primes exhibit a property similar to the Zero Factor Property (ZFP) that we discussed earlier:

• ZFP: If \( ab = 0 \), then \( a = 0 \) or \( b = 0 \).
• Prime Property: If \( p \mid ab \), then \( p \mid a \) or \( p \mid b \) (where \( p \) is prime).

This property of primes plays a key role in many divisibility arguments and is fundamental to number theory.

Example: Solving a Modular Equation

We can apply this property of primes to solve an equation involving the prime number 7. Let’s find the integers such that \( X^2 - 5X + 6 \) is a multiple of 7.

Since 7 is prime, we start by factoring the quadratic:

Then, by the prime property:

This gives us two cases:

• \( X - 3 = 7k \) for some \( k \in \mathbb{Z} \), so \( X = 7k + 3 \).
• \( X - 2 = 7k \) for some \( k \in \mathbb{Z} \), so \( X = 7k + 2 \).

Thus, \( X \) has a remainder of 2 or 3 when divided by 7.

The Fundamental Theorem of Arithmetic (Thm 1.8)

Theorem: Every integer, except for 0 and \( \pm 1 \), can be expressed uniquely as a product of prime numbers. This is known as the Fundamental Theorem of Arithmetic, and it establishes the foundation of prime factorization.

Example: Prime Factorization of 7

As an example, let’s consider the number 7. Can it be expressed as a product of primes? Yes, it’s simply a product of one prime—7 itself. This satisfies the uniqueness property because prime numbers are their own prime factors.

Uniqueness in Prime Factorization

While the order of multiplication does not affect the product, the set of prime factors is unique up to the order of the factors. For example:

illustrates that while we can rearrange or use negatives, the prime factorization remains essentially the same.

Example: Factorization of 40

Consider the number 40. Its prime factorization is:

If we square this number, the prime factorization becomes:

Lemma: Squared Integers

Lemma: A squared integer will always have an even number of each prime factor. This follows directly from the rules of exponents: squaring a number doubles the exponent of each prime factor in its prime factorization.

Theorem: \( \sqrt{2} \) is Irrational

We will now prove that \( \sqrt{2} \) is irrational using a proof by contradiction. This result is fundamental to the study of irrational numbers and demonstrates the power of prime factorization.

Proof (By Way of Contradiction - BWOC)

Suppose, for the sake of contradiction, that \( \sqrt{2} \in \mathbb{Q} \). This means that we can express \( \sqrt{2} \) as a fraction:

where \( a, b \in \mathbb{Z} \) and \( b \neq 0 \). Squaring both sides, we get:

This equation implies that \( a^2 \) is even, meaning \( a \) must be even (since the square of an odd number is odd). So, let \( a = 2k \) for some \( k \in \mathbb{Z} \). Substituting into the equation gives:

This shows that \( b^2 \) is also even, so \( b \) must be even as well. Thus, both \( a \) and \( b \) are even, meaning that the fraction \( \frac{a}{b} \) is not in lowest terms, contradicting the assumption that \( \sqrt{2} \) is rational. Therefore, \( \sqrt{2} \) is irrational. \( \blacksquare \)

Prime Factor Counting Function

We define a function \( N: \mathbb{Z} \to \mathbb{N} \) that counts the number of factors of 2 in a given integer:

Properties of the Function \( N \)

This function satisfies the following properties:

• \( N(ab) = N(a) + N(b) \), which states that the number of factors of 2 in the product of two numbers is the sum of the number of factors in each individual number.
• \( N(a^2) = 2N(a) \), since squaring a number doubles the exponent of each prime factor.
• \( N(2b^2) = N(2) + N(b^2) = 1 + 2N(b) \), illustrating how the function behaves when applied to products involving powers of 2.

Example: Counting Prime Factors of 12

Let’s apply the function \( N \) to the number 12. Since:

we find that \( N(12) = 2 \), because 12 contains two factors of 2.