Prime numbers are the foundation of number theory. We learn important theorems about primes and methods of proof.
Definition and Basic Properties of Prime Numbers
Prime number: a natural number greater than 1 with no divisors other than 1 and itself
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
Infinitude of Primes (Euclid’s Proof): There are infinitely many prime numbers.
Example ① (Proof of the Infinitude of Primes)
Proof by contradiction: Assume there are finitely many primes (p₁, p₂, …, pₙ).
Let N = p₁×p₂×…×pₙ + 1.
N is not divisible by any pᵢ (the remainder is 1).
→ The prime factors of N include a prime outside the list → contradiction → There are infinitely many primes ■
Proof by contradiction: Assume there are finitely many primes (p₁, p₂, …, pₙ).
Let N = p₁×p₂×…×pₙ + 1.
N is not divisible by any pᵢ (the remainder is 1).
→ The prime factors of N include a prime outside the list → contradiction → There are infinitely many primes ■
Testing for Primality
To determine whether n is prime: check whether it is divisible by any prime number less than or equal to √n
Example ② (Primality Test)
Determine whether 127 is prime.
√127 ≈ 11.3. Check divisibility by 2,3,5,7,11:
127÷2=63.5（×）,127÷3（1+2+7=10:×）,127÷5（last digit 2,7:×）
127÷7=18.1…（×）,127÷11=11.5…（×）
Answer:127 is aprime number
Determine whether 127 is prime.
√127 ≈ 11.3. Check divisibility by 2,3,5,7,11:
127÷2=63.5（×）,127÷3（1+2+7=10:×）,127÷5（last digit 2,7:×）
127÷7=18.1…（×）,127÷11=11.5…（×）
Answer:127 is aprime number
Key Points
- Primality test: trial division by primes up to √n
- The only even prime is 2
- All primes greater than or equal to 3 are odd
- “If p is prime and p|ab, then p|a or p|b” (important theorem)
Practice Problems
- Determine whether 101 is prime.
- Show that if p is prime and p|n², then p|n.
- Show that the only pair of consecutive integers n and n+1, both at least 2, that are both prime is n=2.
Answers and Explanations
- √101≈10.05. Check 2,3,5,7: 101÷7=14.4…（×）→ 101 is prime
- p|n² = p|n×n. Since p is prime, p|n or p|n → p|n ■
- When n≥3, at least one of n or n+1 is even (consecutive integers). The only even prime is 2 → n=2 or n+1=2. n=2 → n+1=3 (both are prime ✓). n+1=2 → n=1 (not prime×). Only n=2 ■