Prime Number Guides – Methods, Concepts and Explanations

Prime numbers are positive integers greater than 1 with exactly two positive divisors: 1 and themselves. The definition is directly related to divisibility, factorization, primality testing, and the structure of integers.

Prime number definition

A prime number has exactly two positive divisors. Those divisors are 1 and the number itself. If another positive integer divides the number evenly, the number is composite.

For example, 2, 3, 5, 7, 11, and 13 are prime. The number 4 is composite because 2 divides it. The number 9 is composite because 3 divides it. The number 15 is composite because it is divisible by both 3 and 5.

Numbers that require special treatment

Why 1 is not a prime number

1 is not prime because it has only one positive divisor: 1 itself. A prime number must have exactly two positive divisors.

Excluding 1 from the set of primes also preserves unique prime factorization. The prime factorization of 6 is 2 × 3. If 1 were treated as prime, the same number could also be written as 1 × 2 × 3, 1 × 1 × 2 × 3, and indefinitely many similar forms.

Why 2 is the only even prime

2 is the only even prime. Its positive divisors are 1 and 2. Every even integer greater than 2 is divisible by 2 in addition to 1 and itself, making it composite.

Prime lists therefore begin with 2 and contain only odd numbers after it. Being odd does not prove primality. For example, 9, 15, 21, and 25 are all odd composite numbers.

Zero and negative integers

Prime numbers are positive integers greater than 1. Zero, 1, fractions, decimals, and negative integers are not prime numbers.

A negative integer can be expressed using prime factors together with a factor of −1. For example, −15 = −1 × 3 × 5. The number −15 itself is not classified as prime under the usual definition.

Primality testing methods

Primality testing determines whether one integer is prime. Factorization identifies factors of a composite number, while sieve methods identify many primes within a range.

Trial division

Trial division tests whether smaller positive integers divide a number evenly. If a divisor other than 1 and the number itself is found, the number is composite. If no possible divisor exists, the number is prime.

For example, 91 is divisible by 7. Since 91 = 7 × 13, the number is composite. Finding 7 is enough to settle the primality test; a complete factorization is not required merely to show that 91 is not prime.

Why trial division stops at the square root

Possible divisors only need to be tested through the square root of the number. Every composite integer has at least one factor at or below that limit.

Suppose an integer n is composite and n = a × b, where a and b are integers greater than 1. If both a and b were greater than √n, then their product would be greater than n. At least one factor must therefore be less than or equal to √n.

If no integer from 2 through √n divides n evenly, no undiscovered larger divisor can exist without a matching smaller factor. The number is prime.

Sieve methods

Sieve methods identify many primes within a range. The best-known example is the Sieve of Eratosthenes. It begins with a sequence of integers and removes multiples of successive primes.

To find all primes up to 100, multiples of 2 greater than 2 are removed first. Multiples of 3 greater than 3 are then removed, followed by multiples of 5 and 7 that have not already been removed.

Processing can stop after primes through √100, which is 10. Any composite integer not exceeding 100 must contain a prime factor no greater than its square root.

Sieve methods are suited to prime tables, prime lists below a limit, and calculations requiring many primes in one interval.

Large-number primality tests

Very large integers can require methods faster than ordinary trial division. Testing possible divisors individually becomes inefficient as the input grows.

The Miller–Rabin test is a probabilistic primality test that can identify composite numbers quickly. Numbers that pass are described as probable primes. Repeating the test with suitable bases can reduce the probability that a composite number passes undetected to a very small level.

Deterministic algorithms and primality certificates can be used when a mathematically verified prime result is required. The definition of primality remains the same regardless of the testing algorithm.

Divisibility filters for prime candidates

Several elementary divisibility rules can eliminate composite numbers before longer testing is needed. Passing these checks does not by itself prove that a number is prime.

• Except for 2, every prime is odd. An odd integer can still be composite.
• No prime greater than 5 ends in 0, 2, 4, 5, 6, or 8. In base 10, a prime greater than 5 must end in 1, 3, 7, or 9.
• If the sum of the digits is divisible by 3, the number is divisible by 3. It is composite unless the number itself is 3.
• An integer ending in 0 or 5 is divisible by 5. It is composite unless the number itself is 5.

For example, 91 is odd, ends in 1, and has a digit sum of 10. It is not divisible by 2, 3, or 5. It is still composite because 91 = 7 × 13.

Composite numbers and prime factorization

Composite numbers

A composite number is an integer greater than 1 with more than two positive divisors. It can be written as a product of two smaller positive integers greater than 1.

For example, 35 is composite because 35 = 5 × 7. Finding either 5 or 7 as a nontrivial divisor proves that 35 is not prime.

Prime factorization

Every integer greater than 1 can be expressed as a product of prime numbers. Apart from the order of the factors, that prime factorization is unique.

For example, 84 = 2 × 2 × 3 × 7. Using exponents, the same factorization is written as 2² × 3 × 7.

Prime factorization is used in calculations involving greatest common divisors, least common multiples, fraction simplification, and divisibility.

Coprime numbers

Two integers are coprime when their greatest common divisor is 1. The individual numbers do not need to be prime.

For example, 8 and 15 are both composite, but they have no positive common divisor greater than 1. Therefore, gcd(8,15) = 1 and the numbers are coprime.

Prime gaps and special types of primes

Prime gaps

A prime gap is the difference between consecutive prime numbers. The consecutive primes 11 and 13 have a gap of 2, while 23 and 29 have a gap of 6.

Prime gaps are not constant. Consecutive primes can be close together or separated by several composite integers.

Twin primes

Twin primes are pairs of prime numbers differing by 2. Examples include 3 and 5, 5 and 7, 11 and 13, and 17 and 19.

Mersenne primes

A Mersenne number has the form 2^p − 1. When such a number is prime, it is called a Mersenne prime.

If 2^p − 1 is prime, then p must itself be prime. A prime exponent does not guarantee that the resulting Mersenne number is prime. For example, 2¹¹ − 1 = 2047 = 23 × 89.

Prime numbers in arithmetic and modular arithmetic

Prime numbers determine the prime factorizations of integers greater than 1. They are therefore directly involved in divisibility, greatest common divisors, least common multiples, factor trees, and fraction reduction.

Prime moduli also have a useful property in modular arithmetic. If p is prime, every nonzero residue modulo p has a multiplicative inverse.

For example, modulo 7, the nonzero residue 3 has inverse 5 because 3 × 5 = 15 and 15 ≡ 1 (mod 7). Such properties appear throughout number theory and in cryptographic calculations.

Large primes are used in several cryptographic systems, although cryptography depends on more than primality alone. The relevant constructions use modular arithmetic, factorization properties, discrete logarithms, or related number-theoretic problems depending on the system.

Euclid’s proof that there are infinitely many primes

Prime numbers have been studied for more than two thousand years. One classical result is that there are infinitely many prime numbers.

Euclid’s argument begins by assuming that there is a finite list containing every prime. Multiply all primes on the supposed complete list together and add 1.

The resulting number leaves a remainder of 1 when divided by every prime on the list, so none of those listed primes can divide it evenly.

The new number must either be prime itself or have a prime divisor that was not included in the original list. Either possibility contradicts the assumption that the list contained every prime. Therefore, no finite list can contain all primes.

Examples of primality testing

Trial division can verify primality or compositeness directly for smaller integers.

• 97: √97 is less than 10. Testing the prime divisors 2, 3, 5, and 7 finds no divisor, so 97 is prime.
• 121: √121 = 11, and 121 = 11 × 11, so 121 is composite.
• 143: 143 = 11 × 13, so it is composite.
• 149: √149 is a little above 12. Testing 2, 3, 5, 7, and 11 finds no divisor, so 149 is prime.

A composite result can be verified by displaying a nontrivial factor or factor pair. A prime result from trial division is established when every required divisor through √n has been tested without finding an exact division.