Number Theory

Why Number Theory in Quant Interviews?

Number theory problems test logical reasoning and pattern recognition under pressure. They appear in brainteaser rounds at firms like Jane Street, Citadel, and Two Sigma — not because you'll use modular arithmetic in production code, but because the thinking patterns transfer directly to combinatorial and algorithmic problems.

Modular Arithmetic

The modulo operation gives the remainder after division: $a \bmod n = r$ means $a = qn + r$ for some integer $q$, with $0 \leq r < n$.

Key properties:

• $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$
• $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$
• $(a^k) \bmod n$ can be computed efficiently via repeated squaring in $O(\log k)$ steps

Example — Last digit of $7^{100}$. The last digit is $7^{100} \bmod 10$. The powers of 7 mod 10 cycle: $7, 9, 3, 1, 7, 9, 3, 1, \ldots$ with period 4. Since $100 = 4 \times 25$, we get $7^{100} \bmod 10 = 1$.

Interview Tip: When asked about last digits, think mod 10. When asked about divisibility, think mod $n$. Identifying the cycle length is usually the key step.

Divisibility Rules

Quick tests without division:

• By 3 or 9: Sum the digits. If the sum is divisible by 3 (or 9), so is the number.
• By 4: Check the last two digits.
• By 7: No simple rule — use modular arithmetic directly.
• By 11: Alternating sum of digits. If $d_1 - d_2 + d_3 - d_4 + \cdots$ is divisible by 11, so is the number.

The Euclidean Algorithm

To find $\gcd(a, b)$: repeatedly replace the larger number with the remainder of dividing the two:

$\gcd(a, b) = \gcd(b, a \bmod b), \quad \gcd(a, 0) = a.$

Example. $\gcd(84, 36) = \gcd(36, 12) = \gcd(12, 0) = 12$.

The extended Euclidean algorithm finds integers $x, y$ such that $ax + by = \gcd(a, b)$. This has applications in cryptography and modular inverses.

Fermat's Little Theorem

If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod{p}$.

This is the workhorse for simplifying large exponents mod a prime.

Example. $2^{100} \bmod 13$: since 13 is prime, $2^{12} \equiv 1 \pmod{13}$. Then $100 = 12 \times 8 + 4$, so $2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13}$.

Euler's Totient and Euler's Theorem

When the modulus is composite, Fermat's little theorem doesn't apply directly. Euler's totient $\varphi(n)$ counts the integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$:

• $\varphi(p) = p - 1$ for prime $p$.
• $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.
• $\varphi$ is multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m, n) = 1$.

So for $n = p_1^{a_1} \cdots p_r^{a_r}$, $\varphi(n) = n \prod_i (1 - 1/p_i)$.

Example. $\varphi(12) = \varphi(4)\varphi(3) = 2 \cdot 2 = 4$ (the coprime classes are $\{1, 5, 7, 11\}$).

Euler's theorem (generalization of Fermat). If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

Example. $7^{1000} \bmod 12$: $\gcd(7, 12) = 1$ and $\varphi(12) = 4$, so $7^4 \equiv 1 \pmod{12}$. Then $7^{1000} = (7^4)^{250} \equiv 1 \pmod{12}$.

Fast Modular Exponentiation

To compute $a^k \bmod n$ when $k$ is huge, use repeated squaring -- $O(\log k)$ multiplications instead of $O(k)$:

function modpow(a, k, n):
    result = 1
    a = a mod n
    while k > 0:
        if k is odd:
            result = (result * a) mod n
        a = (a * a) mod n
        k = k // 2     # integer division
    return result

This is the algorithm Fermat's-test-based primality checks (Miller--Rabin) use, and it's the basis of every cryptographic protocol that requires $a^k \bmod n$ for thousand-digit $n$.

Example. $3^{13} \bmod 7$ via repeated squaring: write $13 = 1101_2$, so $3^{13} = 3^8 \cdot 3^4 \cdot 3^1$. Compute $3^2 = 9 \equiv 2$, $3^4 \equiv 4$, $3^8 \equiv 16 \equiv 2 \pmod 7$. Then $3^{13} \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7$. ✓ (Direct check: $3^{13} = 1{,}594{,}323 = 227{,}760 \cdot 7 + 3$.)

Worked Interview Problem

Is $n = 1{,}000{,}001$ divisible by 101?

$1{,}000{,}001 = 10^6 + 1$. We need $10^6 + 1 \bmod 101$. By Fermat's little theorem, $10^{100} \equiv 1 \pmod{101}$. Check: $10^2 = 100 \equiv -1 \pmod{101}$, so $10^4 \equiv 1 \pmod{101}$, and $10^6 = (10^4)(10^2) \equiv 1 \times (-1) = -1 \pmod{101}$. Thus $10^6 + 1 \equiv 0 \pmod{101}$. Yes, it is divisible.