Fix the mistake: Properties of Integers ③ (Advanced)

Properties and Proofs of Prime Numbers

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 ■

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
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

  1. Determine whether 101 is prime.
  2. Show that if p is prime and p|n², then p|n.
  3. 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

  1. √101≈10.05. Check 2,3,5,7: 101÷7=14.4…（×）→ 101 is prime
  2. p|n² = p|n×n. Since p is prime, p|n or p|n → p|n ■
  3. 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 ■

Math (Math A): related lessons