Number Theory Basics for Algorithms

Divisibility and GCD

If a = bq + r, then a number divides both a and b exactly when it divides b and r. Therefore gcd(a,b) = gcd(b,a mod b). Repeating this Euclidean step reaches the GCD in logarithmic time.

For non-zero values, gcd(a,b) × lcm(a,b) = absolute(a × b). In fixed-width languages compute absolute(a / gcd × b) to reduce overflow risk.

Prime sieves

The Sieve of Eratosthenes marks composites below n. When p remains unmarked, begin crossing out at p²: smaller multiples already have a smaller prime factor. The running time is O(n log log n), much faster than trial-dividing every candidate independently.

A smallest-prime-factor sieve also supports rapid factorisation of many values. For one large value, trial division only needs candidates through √n.

Modular arithmetic

Reduce after addition and multiplication: (a + b) mod m and (a × b) mod m depend only on the reduced operands. Subtraction may become negative in some languages, so normalise with (value % m + m) % m.

Division is not ordinary integer division. A modular inverse exists only under the required coprimality conditions; with prime modulus p and non-zero a, Fermat gives a^(p−2) mod p.

Binary exponentiation

Write the exponent in binary. Square the base for each bit and multiply it into the answer when the bit is 1. This reduces exponentiation from O(exponent) multiplications to O(log exponent).

Euclid example

import math
print(math.gcd(48,18))

6

Common traps

Clarify whether a range is below n or through n, handle 0 and 1 explicitly, avoid floating-point square-root boundaries, and consider overflow before multiplication. For negative inputs, define whether remainder and GCD results must be normalised.

Practice Greatest Common Divisor and LCM, Count Primes with a Sieve, and Fast Modular Exponentiation.