Skip to content
Tutorials Center
My learning

Topics

Lesson 177 of 225 ยท Math and Bit Manipulation

Number Theory Basics

Number theory in Python for DSA: Euclid's gcd and lcm, primality tests, the sieve of Eratosthenes, prime factorization, modular arithmetic and modular inverse.

A surprising number of algorithm problems hide a little arithmetic: "how many fractions are in lowest terms", "list all primes below a million", "give the answer modulo 1,000,000,007". The tools for these are old and small. Euclid's algorithm is over two thousand years old, and the sieve of Eratosthenes is nearly as ancient, yet both are exactly what you use today.

This lesson builds those tools from scratch in Python: gcd and lcm, primality testing, the sieve, prime factorization, and modular arithmetic including pow(a, b, m) and the modular inverse. Each one has a slow, obvious version first, then the fast one, with costs counted so you can see the difference.

Divisibility, gcd and lcm

a divides b when b % a == 0. The greatest common divisor gcd(a, b) is the largest number dividing both. The least common multiple lcm(a, b) is the smallest positive number both divide.

Brute force

Try every candidate from min(a, b) downward until one divides both. That takes up to min(a, b) steps, far too slow for big inputs.

Euclid's algorithm

The key fact: gcd(a, b) == gcd(b, a % b). Any number dividing both a and b also divides the remainder a - q*b, and vice versa. Repeat until the remainder is 0:

TEXT
gcd(48, 18):
  48 = 2 * 18 + 12    ->  gcd(18, 12)
  18 = 1 * 12 +  6    ->  gcd(12, 6)
  12 = 2 *  6 +  0    ->  gcd(6, 0) = 6

Each step at least halves the larger number every two rounds, so the number of steps is O(log min(a, b)). The worst case is two consecutive Fibonacci numbers.

Python Brute-force gcd vs Euclid, counting steps

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 run shows the gap: for 1,000,000 and 999,983 the brute force takes 999,983 steps and Euclid takes 5; for the Fibonacci pair 832,040 and 514,229 (the worst case) Euclid still needs only 28.

The lcm follows from gcd(a, b) * lcm(a, b) == a * b. Divide first to keep numbers small: a // gcd(a, b) * b. Python has math.gcd and math.lcm (accepting many arguments in 3.9+).

Python gcd, lcm and reducing fractions

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.

Primality

A prime is an integer greater than 1 whose only positive divisors are 1 and itself.

Trial division

The obvious test tries every divisor up to n - 1: O(n). Two observations shrink it a lot:

  1. Divisors come in pairs: if d divides n, so does n // d. One of a pair is at most sqrt(n), so checking up to sqrt(n) is enough.
  2. After 2, only odd divisors need checking.

That gives O(sqrt n) time.

Python Primality by trial division

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.

Use math.isqrt, the exact integer square root. int(n ** 0.5) can be off by one for large n because of floating-point rounding.

The sieve of Eratosthenes

To list all primes up to n, testing each number separately costs about n * sqrt(n). The sieve does far better by crossing out multiples. Start with every number marked prime. Take the smallest unmarked number p, which must be prime, and cross out p*p, p*p+p, p*p+2p, .... Repeat for each p up to sqrt(n).

TEXT
n = 30   (x = crossed out)
2  3  4x 5  6x 7  8x 9x 10x 11 12x 13 14x 15x 16x 17 18x 19 20x
21x 22x 23 24x 25x 26x 27x 28x 29 30x

p = 2 removes 4, 6, 8, ...        p = 3 removes 9, 12, 15, ...
p = 5 removes 25, 30              p = 7 > sqrt(30), stop
primes: 2 3 5 7 11 13 17 19 23 29

Starting at p*p is safe: a smaller multiple like p*3 already has a smaller prime factor and was crossed out earlier. The total work is about O(n log log n), almost linear, with O(n) space.

Python Sieve of Eratosthenes with a work counter

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 is perfect when you need many primality answers at once: build it once, then each query is a list lookup.

Smallest prime factor sieve

A variation stores, for every number, its smallest prime factor. This lets you factorize any number up to n in O(log n) steps.

Python Smallest prime factor sieve

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.

Prime factorization

Every integer greater than 1 is a product of primes in exactly one way (the fundamental theorem of arithmetic). For a single number, trial division up to sqrt(n) works: divide out each factor completely before moving on, and if something greater than 1 remains at the end, it is a prime.

Python Factorize a single number

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.

Time is O(sqrt n) in the worst case (when n is prime).

Modular arithmetic

Many problems say "return the answer modulo m" because the true answer is gigantic. The % operator gives the remainder, and these identities let you reduce at every step instead of at the end:

TEXT
(a + b) % m == ((a % m) + (b % m)) % m
(a * b) % m == ((a % m) * (b % m)) % m
(a - b) % m == ((a % m) - (b % m)) % m      # Python result is never negative

In Python, % with a positive modulus always returns a value from 0 to m - 1, even for negative left sides (-7 % 5 == 3). In C and Java the result can be negative, which is a classic source of bugs when porting code.

Division is the exception: (a / b) % m is not (a % m) / (b % m). You need a modular inverse.

Fast modular power

pow(a, b, m) computes a**b % m without building the huge number, using fast exponentiation.

Python Modular arithmetic and pow

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.

Modular inverse

The inverse of a modulo m is the number x with a * x % m == 1. It exists exactly when gcd(a, m) == 1. Python 3.8+ computes it with pow(a, -1, m).

When m is prime, Fermat's little theorem gives a**(m-1) % m == 1 for a not divisible by m, so the inverse is pow(a, m - 2, m). The extended Euclidean algorithm finds it for any coprime pair by also tracking the coefficients.

Python Three ways to get a modular inverse

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.

A common use is computing a binomial coefficient or a ratio modulo a prime without any big-number division. See combinatorics.

Common mistakes

  • Looping to n instead of sqrt(n) in primality or factorization.
  • int(n ** 0.5) for large n. Use math.isqrt.
  • Forgetting that 1 is not prime and 2 is the only even prime.
  • Starting the sieve inner loop at 2*p instead of p*p. It still works but does extra writes.
  • Dividing under a modulus with // or /. Multiply by the modular inverse instead.
  • Reducing too late. Taking % m only at the end means Python builds a huge integer first. Reduce after every multiplication.
  • Assuming an inverse exists. a and m must be coprime; for a composite m, Fermat's shortcut does not apply.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many steps does Euclid's algorithm need for gcd(a, b)?

    Every two steps at least halve the larger number, so the step count is logarithmic.
  2. 2. Why is it enough to test divisors up to sqrt(n) when checking whether n is prime?

    If n = d * e with both larger than sqrt(n), the product would exceed n. So some divisor is at most sqrt(n).
  3. 3. Where does the sieve of Eratosthenes start crossing out multiples of a prime p?

    Smaller multiples of p, such as 3p, have a smaller prime factor and were already crossed out. Starting at p * p avoids redundant work.
  4. 4. What does -7 % 5 evaluate to in Python?

    Python's % takes the sign of the divisor, so the result is in 0..4. That is 3, because -7 = -2 * 5 + 3.
  5. 5. When does a modular inverse of a modulo m exist?

    a * x is 1 modulo m only if a and m share no common factor. When m is prime, every a not divisible by m qualifies.

Summary

  • gcd(a, b) = gcd(b, a % b) (Euclid) runs in O(log min(a, b)); lcm = a // gcd * b. Use math.gcd and math.lcm.
  • Test primality by trial division up to isqrt(n) in O(sqrt n).
  • The sieve of Eratosthenes lists all primes up to n in about O(n log log n) time and O(n) space; a smallest-prime-factor sieve factorizes numbers quickly.
  • Factor a single number by dividing out each d up to sqrt(n); a leftover above 1 is prime.
  • Reduce modulo m after every addition and multiplication; Python's % is never negative for positive m.
  • pow(a, b, m) is fast modular exponentiation; pow(a, -1, m) is the inverse when gcd(a, m) = 1, and pow(a, m - 2, m) works for prime m.

Next: Fast Exponentiation and Matrix Power