Divisibility & Primes
Reference · Number Theory · Always free
Study divisibility rules, prime numbers, and the Fundamental Theorem of Arithmetic
Overview
The Integers
Number theory is the study of integers and their properties. It is one of the oldest branches of mathematics and has become unexpectedly important in modern cryptography and computer science. The security of your online transactions depends on number theory!
Definition
Divisibility
For integers a and b with a ≠ 0, we say a divides b (written a | b) if there exists an integer k such that b = a × k.
Equivalently, b/a is an integer.
Examples: 3 | 12 (because 12 = 3 × 4), but 5 ∤ 12 (12/5 is not an integer).
Theorem
Properties of Divisibility
If a | b and a | c, then a | (b + c) and a | (b - c). If a | b, then a | (b × c) for any integer c. If a | b and b | c, then a | c (transitivity). If a | b and b | a, then a = ±b.
Every integer a divides 0 (since 0 = a × 0). 1 divides every integer.
Definition
Prime and Composite Numbers
An integer p > 1 is prime if its only positive divisors are 1 and p. An integer n > 1 that is not prime is composite.
The first primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... Note: 2 is the only even prime. 1 is neither prime nor composite.
Theorem
Fundamental Theorem of Arithmetic
Every integer n > 1 can be written uniquely (up to ordering) as a product of prime powers - each prime raised to a positive integer exponent.
Examples: 60 = 2² × 3 × 5 84 = 2² × 3 × 7 100 = 2² × 5² 360 = 2³ × 3² × 5
The factorization is unique: no two different sets of primes and exponents produce the same integer.
Definition
The Division Algorithm
For any integers a and d with d > 0, there exist unique integers q (quotient) and r (remainder) such that:
a = d × q + r, where 0 ≤ r < d.
We write q = a div d and r = a mod d.
Example: 17 divided by 5: 17 = 5 × 3 + 2, so q = 3, r = 2.
Example
Testing Primality
To check if n is prime, test divisibility by all primes up to √n.
Is 97 prime? √97 ≈ 9.85. Check primes ≤ 9: 2, 3, 5, 7. 97/2 = 48.5 ✗ 97/3 = 32.3... ✗ 97/5 = 19.4 ✗ 97/7 = 13.86... ✗
None divide evenly, so 97 is prime.
Note
The Sieve of Eratosthenes
To find all primes up to n: 1. List integers from 2 to n. 2. The smallest unmarked number is prime. Mark all its multiples. 3. Repeat until you pass √n. 4. All remaining unmarked numbers are prime.
This ancient algorithm (c. 240 BCE) is still efficient for generating primes.