Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 68 · Number Theory

Divisibility and Primes

Learn divisibility, the division algorithm, primes, the Fundamental Theorem of Arithmetic, prime factorization, the sieve of Eratosthenes and primality tests.

Number theory studies the whole numbers and the patterns hidden in how they divide each other. It sounds old-fashioned, but it quietly powers modern computing: hash tables use remainders, schedulers use cycles, and the encryption that protects your bank connection rests on the difficulty of splitting large numbers into primes.

Everything begins with one relation, divisibility, and one family of special numbers, the primes. In this lesson you will learn the basic rules of divisibility, the division algorithm, the Fundamental Theorem of Arithmetic, and practical Python tools for factoring, sieving and testing primality.

Divisibility

For integers a and b with a ≠ 0, we say a divides b, written a | b, if there is an integer k with b = a × k. Then a is a divisor (or factor) of b, and b is a multiple of a. Every integer divides 0, and 1 divides everything. Note that a | b is a statement, while a / b is a number.

A few rules are used constantly and each has a one-line proof by unpacking the definition (see How Proofs Work):

  • If a | b and a | c, then a | (b + c), and more generally a | (bx + cy) for any integers x and y.
  • If a | b and b | c, then a | c (transitivity).
  • If a | b and b ≠ 0, then |a| ≤ |b|.
  • If a | b and b | a, then a = ±b.

For example, if b = ak and c = am, then bx + cy = a(kx + my), a multiple of a. These rules are the same ones you checked when studying Relations: divisibility on the positive integers is reflexive, antisymmetric and transitive, which makes it a partial order.

Python Divisors and the divisibility rules

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The divisors function only loops up to the square root: divisors come in pairs d and n // d, and one of the two is at most √n.

The division algorithm

Dividing 17 by 5 gives quotient 3 and remainder 2, because 17 = 5 × 3 + 2. The division algorithm states that this works for any integers:

Theorem. For integers a and d > 0, there exist unique integers q (the quotient) and r (the remainder) such that a = dq + r and 0 ≤ r < d.

Despite its name it is a theorem, not an algorithm: it says the pair exists and is unique. The remainder is always non-negative and smaller than the divisor, even when a is negative. For a = -17 and d = 5 we get -17 = 5 × (-4) + 3, so q = -4 and r = 3.

Python follows exactly this convention for a positive divisor: // is floor division and % returns a remainder with the sign of the divisor, so divmod(-17, 5) gives (-4, 3). Some other languages (C, Java) truncate toward zero and give a negative remainder, which is a classic source of bugs.

Python The division algorithm in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four tools for remainders

a // d The quotient q, rounded down.
a % d The remainder r, from 0 to d-1.
divmod(a, d) Both at once.
d | a Same as a % d == 0.
1 / 2

Primes and composites

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 number 1 is neither prime nor composite, and 2 is the only even prime. The primes begin 2, 3, 5, 7, 11, 13, 17, 19, 23, … and, as Contradiction and Contrapositive showed, they never run out.

A key fact: if n is composite, it has a divisor d with 2 ≤ d ≤ √n. If both factors in n = a × b were larger than √n, their product would exceed n. So to test whether n is prime, trial division need only try divisors up to √n.

The Fundamental Theorem of Arithmetic

Theorem. Every integer n > 1 can be written as a product of primes, and this factorization is unique apart from the order of the factors.

Existence is proved by strong induction (see Strong Induction and Well-Ordering). Uniqueness uses Euclid's lemma: if a prime divides a product, it divides one of the factors. We usually write the factorization in exponent form, such as 360 = 2³ × 3² × 5.

Uniqueness is what makes primes the "atoms" of the integers. It lets you read off divisors, gcds and counts from the exponents. The number of positive divisors of n = p₁^e₁ × … × pₖ^eₖ is (e₁+1)(e₂+1)…(eₖ+1), because a divisor chooses an exponent from 0 to eᵢ for each prime independently. The sum of divisors has a formula too, but the count already gives a nice check.

Python Factorization and the divisor count

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sieve of Eratosthenes

Testing each number separately is wasteful when you want all primes up to a limit. The sieve of Eratosthenes does it by elimination: write the numbers from 2 up to N, take the smallest unmarked number (it is prime), cross out all its multiples, and repeat. You can stop once the prime you are on exceeds √N, since every composite number up to N has a prime factor at most √N, and it was already crossed out by then. For each prime p, start crossing out at p², because smaller multiples have a smaller prime factor and are already gone.

The running time is roughly N log log N, which is close to linear and far better than trial division on every number.

Python Sieve of Eratosthenes

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The counts show the prime number theorem at work: the number of primes up to n, written π(n), is roughly n / ln n. Primes thin out slowly but never stop. Whether there are infinitely many twin primes (pairs like 11 and 13) is an open conjecture, and so is Goldbach's claim that every even number above 2 is the sum of two primes: no counterexample has been found, but nobody has a proof (compare How Proofs Work).

Primality testing

For small numbers, trial division up to √n is enough. For large numbers it is far too slow: a 100-digit number needs about 10⁵⁰ divisions. Practical tests are based on deeper number theory. One useful variant is Fermat's idea: if p is prime and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p). A number that fails this is certainly composite; one that passes is only probably prime. The Miller-Rabin test strengthens this idea and, with fixed bases, is deterministic for all numbers below a large bound. We return to the underlying congruences in Modular Arithmetic and Number Theory in Cryptography.

Python Trial division versus Fermat and Miller-Rabin

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trial division would take about a billion steps to confirm that 2⁶¹ - 1 is prime, yet Miller-Rabin does it with a few dozen modular exponentiations. The number 561 is a Carmichael number: composite, but it passes the Fermat test for every base that shares no factor with it, so Fermat alone is not reliable and Miller-Rabin is the better tool.

The sieve finds all primes up to a limit, trial division factors small numbers, and Miller-Rabin answers "is this one big number prime?". Factoring a big number, as opposed to testing it, is believed to be hard, which is the foundation of RSA.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does a | b mean?

    a | b means there is an integer k with b = a * k, so b is a multiple of a. 3 | 12, but 12 | 3 is false.
  2. 2. What does the division algorithm give for a = -17 and d = 5?

    The remainder must satisfy 0 <= r < d, so -17 = 5 * (-4) + 3. This matches Python's divmod(-17, 5).
  3. 3. How many positive divisors does 360 = 2^3 x 3^2 x 5 have?

    Multiply one more than each exponent: (3+1)(2+1)(1+1) = 4 * 3 * 2 = 24.
  4. 4. In the sieve of Eratosthenes, why can you stop at the square root of N?

    If n <= N is composite, it has a prime factor p with p * p <= n <= N, so n is crossed out by a prime that is at most the square root of N.

Summary

  • a | b means b = a × k for an integer k; divisibility is transitive and respects linear combinations.
  • The division algorithm gives a unique quotient and remainder with 0 ≤ r < d; in Python, divmod and % follow that rule for positive divisors.
  • A prime has exactly two positive divisors; a composite number has a divisor up to its square root.
  • The Fundamental Theorem of Arithmetic: every integer above 1 factors uniquely into primes, and exponents give the divisor count (e₁+1)(e₂+1)….
  • The sieve of Eratosthenes finds all primes up to N in about N log log N steps.
  • Trial division handles small numbers; probabilistic and deterministic tests like Miller-Rabin handle large ones.

Next: GCD, LCM and the Euclidean Algorithm.