Prime and Composite Numbers
Fundamental Definitions
Prime Number
A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.
Formally: $p > 1$ is prime if and only if for all $a, b \in \mathbb{N}$, $p = a \cdot b$ implies $a = 1$ or $b = 1$.
Composite Number
A composite number is a natural number greater than 1 that has more than two distinct positive divisors. In other words, it can be written as a product of two smaller natural numbers.
Formally: $n > 1$ is composite if there exist $a, b \in \mathbb{N}$ with $1 < a, b < n$ such that $n = a \cdot b$.
Special Case: The number 1 is neither prime nor composite. It is called a unit. The number 2 is the only even prime number.
🏛️ Theorem: Infinitude of Primes (Euclid, ~300 BCE)
Theorem. The set of prime numbers is infinite.
Proof (by contradiction):
- Assume, for the sake of contradiction, that there are only finitely many primes: $p_1, p_2, p_3, \ldots, p_n$.
- Consider the number: $$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$
- Now, $N > 1$, so $N$ must either be prime or have a prime factor.
- However, when we divide $N$ by any prime $p_i$ in our list, we get a remainder of 1: $$N \div p_i = (p_1 \cdot p_2 \cdots p_n) / p_i + \frac{1}{p_i}$$ So $p_i \nmid N$ for any $i = 1, 2, \ldots, n$.
- This means $N$ is either a new prime not in our list, or $N$ has a prime factor not in our list.
- Either way, we have found a prime not in our original list — a contradiction. ∎