Prime Number Formulas — Definition, Formula & Examples

Prime number formulas are a collection of well-known results in number theory that describe properties of prime numbers, estimate how many primes exist below a given value, or test whether a number is prime.

These formulas include Wilson's theorem ( $(p-1)! \equiv -1 \pmod{p}$ iff $p$ is prime), the prime number theorem ( $\pi(x) \sim \frac{x}{\ln x}$ as $x \to \infty$ ), and Euler's product formula ( $\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p\,\text{prime}} \frac{1}{1 - p^{-s}}$ for $s > 1$ ), among others.

Key Formula

\text{Wilson's Theorem: } (p-1)! \equiv -1 \pmod{p} \iff p \text{ is prime}

Where:

$p$ = A positive integer being tested for primality
$(p-1)!$ = The factorial of p − 1, i.e., the product 1 · 2 · 3 · … · (p − 1)

How It Works

Different formulas serve different purposes. Wilson's theorem gives an exact primality test: compute

(n-1)!

modulo

n

, and if the result is

n-1

(equivalently

-1

), then

n

is prime. The prime counting function

\pi(x)

counts primes up to

x

, and the prime number theorem approximates it as

\frac{x}{\ln x}

. For example,

\pi(100) = 25

, while

\frac{100}{\ln 100} \approx 21.7

—a rough but useful estimate that improves in relative accuracy for larger

x

. Euler's product formula connects primes to the zeta function and is foundational in analytic number theory.

Worked Example

Problem: Use Wilson's theorem to verify that 7 is prime.

Compute (p−1)!: Calculate 6! = 720.

6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720

Reduce modulo p: Divide 720 by 7. Since 720 = 102 × 7 + 6, the remainder is 6.

720 \mod 7 = 6

Check the condition: Wilson's theorem requires (p−1)! ≡ −1 (mod p). Since −1 ≡ 6 (mod 7), the condition holds.

6 \equiv -1 \pmod{7} \; \checkmark

Answer: Since 6! ≡ −1 (mod 7), Wilson's theorem confirms that 7 is prime.

Why It Matters

These formulas appear throughout number theory courses and competition math. The prime number theorem is central to cryptography, where estimating the density of large primes determines how quickly key-generation algorithms can find them. Wilson's theorem, while computationally expensive, underpins several theoretical proofs about the structure of modular arithmetic.

Common Mistakes

Mistake: Thinking Wilson's theorem is a practical way to test large numbers for primality.

Correction: Computing (n−1)! grows astronomically fast, making this test impractical for large n. It is mainly a theoretical tool. For actual primality testing, algorithms like Miller-Rabin are used instead.