Course contentsShow
← Mathematics
Lesson 2721 of 3,12154. Number TheoryFree lesson

Identifying Primes and Trial Division

Learn systematic methods to test whether a given number is prime using trial division up to the square root.

Identifying Primes and Trial Division

What you'll learn: You'll master a systematic method to determine whether any given number is prime by testing divisibility only up to its square root.

The Core Idea

A prime number has exactly two divisors: 1 and itself. To verify primality, we could test divisibility by every integer from 2 up to n - 1, but that's inefficient. Here's the key insight: if a number n has a divisor greater than √n, it must also have a corresponding divisor smaller than √n.

Why? Because divisors come in pairs. If n = a × b and a > √n, then b must be less than √n (otherwise a × b would exceed n). So we only need to check potential divisors up to √n.

Trial Division Method

Step 1: Check if n ≤ 1. If so, it's not prime.

Step 2: Check if n = 2. If so, it's prime (the only even prime).

Step 3: Check if n is even. If so, it's not prime.

Step 4: Test divisibility by all odd numbers from 3 up to √n. If any divides n evenly, then n is composite. If none do, n is prime.

Example

Is 97 prime?

  • √97 ≈ 9.85, so test divisors up to 9
  • Test 3: 97 ÷ 3 = 32 remainder 1 ✗
  • Test 5: 97 ÷ 5 = 19 remainder 2 ✗
  • Test 7: 97 ÷ 7 = 13 remainder 6 ✗
  • Test 9: 97 ÷ 9 = 10 remainder 7 ✗

Since no divisor worked, 97 is prime.

Key Takeaway: Trial division tests primality efficiently by checking divisibility only up to √n, leveraging the fact that divisors come in pairs split by the square root.