Prime Numbers and Composites: Number Theory Guide Simply

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, 13, and so on. A composite number is an integer greater than 1 that is not prime, meaning it can be split into smaller factors, like 4 = 2 times 2 or 15 = 3 times 5. The number 1 is neither prime nor composite.

Primes matter enormously: they are the atoms of multiplication, and modern internet security (RSA encryption) works precisely because multiplying two large primes is easy while factoring the result back is practically impossible.

Key Concepts

• Prime: exactly two positive divisors (1 and itself).
• Composite: more than two positive divisors; always expressible as a product of smaller integers.
• Unit: 1 (and −1) — excluded from both categories to keep factorisation unique.
• Trial division: to test n, try dividing by primes up to the square root of n; if none divide n, it is prime.
• Infinitely many primes: Euclid proved the primes never run out.

Formulas

• Trial division bound: if n is composite, it has a divisor d with 2 ≤ d ≤ √n.
• So n is prime if no integer from 2 to the square root of n divides it.
• Euclid's proof sketch: given primes p1 through pk, the number N = (p1 times … times pk) + 1 has a prime divisor not in the list — hence no finite list contains all primes.

Worked Example

Is 97 prime? The square root of 97 is about 9.85, so test divisors 2, 3, 5, 7. 97 is odd (not divisible by 2); digit sum 9+7 = 16 is not a multiple of 3; it does not end in 0 or 5; 7 times 13 = 91 and 7 times 14 = 98, so 7 does not divide 97. No divisor found up to the square root, therefore 97 is prime. Contrast 91: its square root is about 9.54, and 7 times 13 = 91, so 91 = 7 times 13 is composite — a classic trap since 91 "looks" prime.

Common Misconceptions

• "1 is prime." It is not — a prime needs exactly two divisors, and 1 has only one. Calling 1 prime would destroy unique factorisation.
• "All primes are odd." 2 is prime and even; it is the only even prime.
• "You must test all numbers below n." Testing up to the square root of n is enough — if n = a times b with both factors above √n, their product would exceed n.

Real-World Applications

• RSA cryptography: public keys are products of two huge secret primes.
• Hashing and random number generation: prime-sized tables reduce collisions.
• Engineering: primes are used wherever periodic interference between cycles must be avoided.

Primes have exactly two divisors, composites have more, and 1 is neither. Trial division up to the square root decides primality, Euclid showed primes are infinite, and their hardness of factoring guards the modern internet.