Math Tools Math Tools
Share:
← Back to Blog

What Makes a Number Prime?

What Makes a Number Prime?

By Math Tools ·

What Makes a Number Prime?

Is 1 a prime number? For centuries, some mathematicians said yes. Today the answer is a firm no, and the reason isn't arbitrary. If 1 counted as prime, one of the most important theorems in all of mathematics would stop being true.

Primes are the building blocks of every whole number, the foundation of internet security, and the subject of some of the oldest unsolved problems in math. Here's what makes a number prime, how to test for it, and why the definition is exactly what it is.

1 Isn't Prime Because It Would Break Arithmetic

The modern definition:

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself.

Why exclude 1? Because of the fundamental theorem of arithmetic: every whole number greater than 1 can be written as a product of primes in exactly one way (ignoring order).

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5

If 1 were prime, uniqueness would collapse:

6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 = …

Every number would have infinitely many "prime factorizations." Rather than add "except for 1" to dozens of theorems, mathematicians simply define primes to start at 2. See the unique factorization of any number with the prime factorization tool.

Primes, Composites and 1

Whole numbers greater than 1 fall into two groups:

  • Prime: exactly two divisors (2, 3, 5, 7, 11, 13, …)
  • Composite: more than two divisors (4, 6, 8, 9, 10, 12, …)

And 1 is neither: it has only one divisor. 0 is neither too.

A few facts worth knowing:

  • 2 is the only even prime. Every other even number is divisible by 2.
  • There are 25 primes below 100.
  • Every prime greater than 3 has the form 6k − 1 or 6k + 1, because numbers of the form 6k, 6k + 2, 6k + 3 and 6k + 4 are divisible by 2 or 3.

Browse them on the list of prime numbers and compare with the composite numbers list.

How to Test Whether a Number Is Prime

Trial Division

The simplest method: try dividing by smaller numbers. But you don't have to try all of them. You only need to check divisors up to √n.

Why? If n = a × b and both a and b were larger than √n, then a × b would be larger than n. So at least one factor must be ≤ √n.

Example: is 221 prime?

√221 ≈ 14.87, so check primes up to 13:

221 ÷ 2  → no (odd)
221 ÷ 3  → no (2 + 2 + 1 = 5, not divisible by 3)
221 ÷ 5  → no (doesn't end in 0 or 5)
221 ÷ 7  → 31.57… no
221 ÷ 11 → 20.09… no
221 ÷ 13 → 17 ✓

221 = 13 × 17, so it's composite. Check it with the prime checker. Square roots help set the limit; see the square roots list.

Quick Divisibility Rules

  • 2: last digit is even
  • 3: digit sum divisible by 3
  • 5: last digit is 0 or 5
  • 11: alternating digit sum divisible by 11 (for 121: 1 − 2 + 1 = 0 ✓)

Testing Enormous Numbers

Trial division is hopeless for numbers with hundreds of digits. Checking up to √n for a 300-digit number means about 10¹⁵⁰ divisions.

Instead, computers use tests based on Fermat's little theorem: if p is prime and a isn't a multiple of p, then:

a^(p−1) ≡ 1 (mod p)

If this fails for some a, n is definitely not prime. The Miller–Rabin test strengthens this idea. Each round that n passes cuts the chance that a composite slipped through by a factor of at least 4. After 40 rounds, the chance of error is below 1 in 10²⁴. That's how your browser generates primes for encryption in milliseconds.

An Insider Reference: PRIMES Is in P

For a long time, it was unknown whether primality could be tested with certainty in a number of steps that grows only polynomially with the number of digits.

In August 2002, Manindra Agrawal and his undergraduate students Neeraj Kayal and Nitin Saxena at the Indian Institute of Technology Kanpur released a paper titled "PRIMES is in P." Their AKS primality test was the first algorithm proven to be general, deterministic and polynomial-time. The paper earned them the 2006 Gödel Prize. In practice, faster probabilistic tests are still used, but AKS settled a fundamental theoretical question.

Two Concepts Worth Knowing

Divisor

A divisor of n is a whole number that divides n with no remainder. The number of divisors decides whether n is prime (2), composite (more than 2), or 1 (exactly 1).

Modular Arithmetic

Modular arithmetic works with remainders. It underlies divisibility rules, Fermat's little theorem and modern primality tests. See the number theory formulas.

Quick Answer: What Makes a Number Prime?

A number is prime if it's a whole number greater than 1 with exactly two positive divisors: 1 and itself. To test a number n, check whether any prime up to √n divides it. If none does, n is prime. The number 1 isn't prime, because that would break unique prime factorization.

Try Them Yourself

Pick a three-digit number, find its square root, and test it by trial division. Then check your answer with the prime checker.

Next → Why There Are Infinitely Many Primes