Number Theory: GCD, Primes, and Modular Arithmetic

Why number theory shows up in interviews

Number theory is the study of the whole numbers and how they divide one another. A handful of its results turn up again and again in coding problems: reducing a fraction to lowest terms, deciding whether a number is prime, listing every prime below some limit, and keeping a huge answer from overflowing by working “modulo” a large number. None of these needs advanced mathematics. Each is a short, exact procedure of a few lines with a clean Big-O cost worth knowing cold.

Throughout we lean on two operators. Integer division // keeps only the whole part (7 // 2 is 3), unlike /, which produces a float (7 / 2 is 3.5). The remainder operator % gives what is left over: 7 % 2 is 1. Keep the distinction between // and / sharp as we go.

Greatest common divisor and the Euclidean algorithm

The greatest common divisor of two integers a and b, written gcd(a, b), is the largest number that divides both of them with no remainder. The gcd of 48 and 18 is 6, because 6 divides both and nothing larger does. Trying every candidate downward from min(a, b) works but is O(n) and slow.

The Euclidean algorithm rests on one fact: any number that divides both a and b also divides a % b, the remainder of a divided by b. Since a = (a // b) * b + (a % b), a divisor d of both a and b divides the (a // b) * b term, so it must divide what is left, a % b. The common divisors of (a, b) are therefore exactly those of (b, a % b), so the two pairs share the same greatest common divisor. We repeat the replacement; because the second number shrinks every round, we quickly reach a remainder of 0. When b is 0 the answer is a, because every number divides 0.

Here is the iterative version, which repeatedly replaces the pair (a, b) with (b, a % b):

def gcd(a, b):
    while b != 0:              # stop when the remainder reaches 0
        a, b = b, a % b        # replace (a, b) with (b, a % b)
    return a                   # the last non-zero value is the gcd

print(gcd(48, 18))   # -> 6
print(gcd(17, 5))    # -> 1
print(gcd(0, 5))     # -> 5

The line a, b = b, a % b is a simultaneous assignment: Python evaluates the right side first, then binds both names, so there is no need for a temporary variable. A gcd of 1, as with 17 and 5, means the two numbers share no factor bigger than 1; such numbers are called coprime.

The same idea reads naturally as a recursion, since the rule refers to itself:

def gcd_rec(a, b):
    if b == 0:                 # base case: gcd(a, 0) is a
        return a
    return gcd_rec(b, a % b)   # recurse on the smaller pair

print(gcd_rec(48, 18))    # -> 6
print(gcd_rec(1071, 462)) # -> 21

Tracing the Euclidean algorithm

Walk the iterative loop on gcd(1071, 462). Each row is the state at the top of the while loop: the current a and b, the remainder a % b we compute, and the new pair we carry into the next round.

Four rounds, and the numbers collapse from the thousands down to 0 fast.

Complexity. Each round replaces the larger number with a remainder, which is always smaller than the divisor. It can be shown that two rounds at most roughly halve the larger value, so the number of rounds is proportional to the number of digits: O(log(min(a, b))) time and O(1) space for the iterative version, far better than testing every candidate.

Least common multiple

The least common multiple of a and b, lcm(a, b), is the smallest positive number that both divide into. It ties to the gcd by a simple identity: a * b counts every factor of both, and dividing out the shared part gcd(a, b) leaves the least common multiple, so lcm(a, b) = a * b // gcd(a, b). The one subtlety is the order of arithmetic: write it as a // gcd(a, b) * b, dividing before multiplying.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b   # divide first, then multiply, to keep values small

print(lcm(4, 6))    # -> 12
print(lcm(21, 6))   # -> 42

Because gcd(a, b) divides a exactly, a // gcd(a, b) has no remainder and loses nothing, and dividing first keeps the intermediate number smaller than the full product a * b. Python integers grow without limit so this cannot overflow, but in fixed-width languages (C, Java, Go) the product a * b can silently wrap around and give a wrong answer, while the divide-first form stays in range. It is a good habit to carry everywhere.

Primality testing by trial division

A prime is an integer greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, .... To test whether a single number n is prime, the direct method is trial division: try to divide n by each candidate and see whether any divides evenly.

The key optimization is that you only need to test divisors up to the square root of n, not all the way to n. Divisors come in pairs: if d divides n, so does n // d, and one member of each pair is at most sqrt(n). So if n had a divisor larger than its square root, it would also have the matching partner below the square root, which we would already have found. Checking up to sqrt(n) therefore catches every factor.

def is_prime(n):
    if n < 2:                  # 0, 1, and negatives are not prime
        return False
    if n < 4:                  # 2 and 3 are prime
        return True
    if n % 2 == 0:             # even numbers above 2 are composite
        return False
    i = 3
    while i * i <= n:          # test odd divisors up to sqrt(n)
        if n % i == 0:
            return False       # found a factor: composite
        i += 2                 # skip even candidates
    return True                # no factor found: prime

print(is_prime(17))   # -> True
print(is_prime(1))    # -> False
print(is_prime(91))   # -> False  (91 = 7 * 13)

The condition i * i <= n is the loop’s way of saying i <= sqrt(n) without computing a square root, which avoids floating-point rounding trouble near the boundary. After ruling out 2, we step i by 2 to skip even candidates, since no even number above 2 can be a factor of an odd n.

Complexity. The loop runs until i passes sqrt(n), so it does about sqrt(n) / 2 iterations: O(sqrt(n)) time and O(1) space. For a single number this is fast enough even when n is in the billions.

The Sieve of Eratosthenes

Trial division answers “is this one number prime?” But problems often ask for every prime up to some limit n. Running is_prime on each value would cost O(n * sqrt(n)). The Sieve of Eratosthenes does the whole job far faster by turning the question around: instead of testing each number for factors, it starts from each prime and crosses out all of its multiples.

Keep a boolean list is_p where is_p[k] starts True. Walk i upward from 2. The first time you reach a number still marked True, it has no smaller factor, so it is prime; cross out all of its multiples, since they each have i as a factor. Whatever survives to the end is prime.

The one clever detail is where to start crossing out. For prime i, every multiple below i * i (2*i, 3*i, up to (i-1)*i) has a smaller factor and was already crossed out when we processed that smaller factor, so we can begin at i * i and skip redundant work.

def sieve(n):
    if n < 2:
        return []
    is_p = [True] * (n + 1)    # index 0..n, all assumed prime to start
    is_p[0] = is_p[1] = False  # 0 and 1 are not prime
    i = 2
    while i * i <= n:          # only sieve up to sqrt(n)
        if is_p[i]:            # i survived, so it is prime
            for j in range(i * i, n + 1, i):   # cross out i*i, i*i+i, ...
                is_p[j] = False
        i += 1
    return [x for x in range(n + 1) if is_p[x]]

print(sieve(30))
# -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The outer loop stops at sqrt(n) for the same reason trial division does: any composite k <= n has a factor no larger than sqrt(n), so it was crossed out by the time i reached that factor. Numbers still marked True above sqrt(n) are therefore already known to be prime, and the final list comprehension collects them.

Complexity. Crossing out the multiples of 2, then 3, then 5, and so on sums to O(n log log n) time, very close to linear and much faster than running is_prime on every value; the boolean list uses O(n) space. The sieve is the right tool whenever you need many primes under a fixed limit; trial division stays better for a single large, isolated number.

Modular arithmetic and the 1_000_000_007 modulus

Many counting problems have answers too large for a fixed-width integer, so the problem asks you to return the answer “modulo 1_000_000_007” — the remainder after dividing the true answer by 1_000_000_007. This constant is a large prime: big enough to make accidental collisions rare, and prime so that division-like operations behave well. Even though Python integers never overflow, applying the modulus keeps the numbers small and matches what the problem’s checker expects.

You can apply the modulus early, not only at the end, because addition and multiplication commute with taking remainders:

(a + b) % m == ((a % m) + (b % m)) % m
(a * b) % m == ((a % m) * (b % m)) % m

So you can reduce as you go, keeping every intermediate value below m instead of letting a running product balloon. Here is a factorial computed modulo the prime, reducing after each multiplication:

def factorial_mod(n, m):
    result = 1
    for k in range(2, n + 1):
        result = (result * k) % m   # reduce every step so result stays < m
    return result

print(factorial_mod(5, 1_000_000_007))    # -> 120
print(factorial_mod(20, 1_000_000_007))   # -> 146326063

The exact value of 20! is 2432902008176640000; taking it modulo 1_000_000_007 gives 146326063, the same number the step-by-step reduction produces. A helpful Python detail: % always returns a non-negative result, even for negative operands (-7 % 3 is 2, not -1). So a subtraction followed by % m stays in the valid range 0..m-1 with no manual correction, which matters for rolling hashes and other running computations.

print(-7 % 3)   # -> 2  (Python's % is always non-negative)

Fast modular exponentiation

Some problems need a large power taken modulo m, such as pow_mod = base ** exp % m where exp is huge. Multiplying base by itself exp times is O(exp) and far too slow. Python’s built-in three-argument pow does it efficiently:

print(pow(2, 10, 1000))          # -> 24   (2**10 = 1024, and 1024 % 1000 = 24)
print(pow(3, 200, 1_000_000_007)) # -> 136318165

pow(base, exp, mod) computes base raised to exp, modulo mod, without ever building the astronomically large intermediate number. It uses square and multiply: reading exp in binary, repeated squaring gives base^1, base^2, base^4, base^8, ..., one per bit position, and you multiply together only the powers whose bit is set, reducing modulo m after each step. That turns exp multiplications into about log2(exp), so the cost is O(log exp).

This underlies the modular inverse: dividing under a prime modulus means multiplying by an inverse, and when m is prime that inverse is pow(a, m - 2, m). Knowing the one-line form exists is usually enough for an interview.

Common pitfalls

• Integer versus float division. / yields a float, // yields an integer. Using / where an index or exact count is needed (total / 2 instead of total // 2) gives a float like 3.0, which then fails as a list index or in an exact comparison. Reach for // whenever the value must stay a whole number.
• Forgetting to reduce intermediate products. In a fixed-width language, letting a running product grow before the final % m overflows and corrupts the answer. Apply % m after each multiplication or addition, not only at the end. Python will not overflow, but reducing as you go keeps the numbers small.
• Sieve starting index. Start crossing out at i * i, not 2 * i (too low still works but repeats effort). Forgetting to mark 0 and 1 as non-prime gives a wrong list.
• sqrt boundary in primality. Use while i * i <= n, not while i <= n ** 0.5; the integer comparison avoids floating-point rounding that can drop a factor exactly at the square root.
• gcd with zero. gcd(a, 0) is a, and gcd(0, 0) is 0. The loop handles both correctly, but do not special-case them into an error.

Big-O summary

Practice

1. Write gcd(a, b) from scratch, both the iterative and the recursive form, and confirm they agree on several pairs including gcd(0, 7), gcd(7, 0), and two coprime numbers like gcd(9, 28). Then use your gcd to build lcm(a, b) and check that lcm(4, 6) is 12.

2. Implement the Sieve of Eratosthenes and use it to count how many primes are below 100 (the answer is 25). Then modify it to also record, for each number, its smallest prime factor, so you can quickly factor any number up to the limit.

3. Compute factorial(50) % 1_000_000_007 two ways: once by building the full factorial and taking the modulus at the end, and once by reducing with % m after each multiplication. Confirm both give the same result, then explain in one sentence why reducing early is preferred in a fixed-width language.