Mathematical Foundations

Interactive notes on modulo, primes, GCD, coprime numbers, base conversion, and polynomials — essential math for competitive programming and interviews.

Math Foundations interactive

Modulo Operator

Real-life analogy: A clock. After 12 hours it wraps back to 1. 17 % 12 = 5. A week has 7 days — day 10 lands on day 10 % 7 = 3 (Wednesday).

Definition

a % m returns the remainder when a is divided by m.

a = q × m + r where 0 ≤ r < m

Live Calculator

a = m =

Key Properties

Distributive

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

Multiplication

(a × b) % m
= ((a%m) × (b%m)) % m

Division — needs Modular Inverse

(a / b) % m ≠ (a%m) / (b%m). Use a × b⁻¹ % m where b⁻¹ is modular inverse (exists only when gcd(b,m)=1).

Modular Exponentiation

Fast power: a^n % m in O(log n)

a ^n % m

def mod_pow(a, n, m):
    result = 1
    a = a % m
    while n > 0:
        if n % 2 == 1:          # odd exponent
            result = (result * a) % m
        n //= 2
        a = (a * a) % m         # square the base
    return result

Common Use Cases

Use Case	Example
Cyclic indexing	`arr[(i+1) % n]` — wrap array
Even/odd check	`n % 2 == 0`
Hashing	`key % bucket_count`
Large number arithmetic	`(a*b) % MOD` — prevent overflow
Calendar / scheduling	`day % 7`

Concept Check

What is (2^10) % 1000?

Interview Tips

Always apply % MOD after every arithmetic op to avoid overflow (use 1e9+7 or 998244353).
Negative modulo: -7 % 3 = -1 in Python/C. Use ((-7) % 3 + 3) % 3 = 2 for always-positive result.
Division in modular arithmetic requires Fermat's little theorem when m is prime.

Prime Numbers

Analogy: Atoms of arithmetic. Every number is built by multiplying primes. Like LEGO blocks — every structure decomposes into its fundamental bricks.

Definition

A number p > 1 is prime if its only divisors are 1 and p itself.

Prime 2, 3, 5, 7, 11, 13, 17, 19, 23...

Composite 4=2×2, 6=2×3, 9=3×3...

Special 1 is neither prime nor composite

Primality Check — Interactive

n =

Brute Force O(n)

for i in range(2, n):
    if n % i == 0:
        return False
return True

Optimized O(√n)

for i in range(2,
    int(n**0.5)+1):
  if n % i == 0:
    return False
return True

Why √n? If n = a × b and both a,b > √n, their product exceeds n. So one factor must be ≤ √n.

Sieve of Eratosthenes — O(n log log n)

Find all primes up to n efficiently.

Create boolean array is_prime[0..n], all True

Set is_prime[0] = is_prime[1] = False

For each prime p from 2 to √n: mark all multiples p², p²+p, p²+2p... as False

Remaining True values are prime

Sieve Demo

Find primes up to

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for mul in range(p*p, n+1, p):
                is_prime[mul] = False
    return [i for i, v in enumerate(is_prime) if v]

Fundamental Theorem of Arithmetic

Every integer > 1 has a unique prime factorization.

Example: 360 = 2³ × 3² × 5

Concept Check

Smallest prime with two digits?

Interview Tips

2 is the only even prime.
For range queries, always precompute with Sieve — don't check each n individually.
Segmented Sieve for very large ranges (when n > 10⁷).
Miller-Rabin for probabilistic primality when n is astronomically large.

GCD — Greatest Common Divisor

Analogy: You have a 12cm and 8cm ribbon. What's the largest ruler that measures both exactly? Answer: 4cm. That's gcd(12, 8) = 4.

Definition

The largest integer that divides both a and b with no remainder.

LCM: lcm(a, b) = (a × b) / gcd(a, b)

Euclidean Algorithm — O(log min(a,b))

Key insight: gcd(a, b) = gcd(b, a % b)

Base case: gcd(a, 0) = a

Step-by-Step Trace

a = b =

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

# Recursive version
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

Extended Euclidean

Finds integers x, y such that: ax + by = gcd(a, b)

Used for: modular inverse, solving linear Diophantine equations.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

GCD Properties

Property	Formula
Commutative	`gcd(a,b) = gcd(b,a)`
Associative	`gcd(a,gcd(b,c)) = gcd(gcd(a,b),c)`
Identity	`gcd(a,0) = a`
Multiple	`gcd(ka, kb) = k × gcd(a,b)`
With LCM	`gcd(a,b) × lcm(a,b) = a × b`

Concept Check

gcd(100, 75) = ?

Interview Tips

Python 3.5+: use math.gcd(a, b) — no need to implement.
GCD of an array: fold left — reduce(gcd, arr).
Extended GCD is the basis for modular inverse computation.
Bézout's identity: solutions to ax + by = c exist iff gcd(a,b) | c.

Coprime Numbers

Analogy: Two gears rotate together cleanly only when their tooth counts share no common factor. Gear designers use coprimality to ensure full mesh patterns.

Definition

Two numbers are coprime (relatively prime) if gcd(a, b) = 1.

They share no common prime factor. Neither needs to be prime itself.

Coprime gcd(8,9)=1, gcd(14,15)=1, gcd(35,36)=1

Not Coprime gcd(6,9)=3, gcd(4,6)=2

Coprime Checker

a = b =

Euler's Totient Function φ(n)

φ(n) = count of integers in [1, n] that are coprime with n.

φ(p) = p - 1          (p is prime)
φ(pᵏ) = pᵏ - pᵏ⁻¹
φ(mn) = φ(m)×φ(n)    (if gcd(m,n)=1)

# General formula
φ(n) = n × ∏(1 - 1/p)  for all prime p|n

φ(n), n =

def euler_totient(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

Fermat's Little Theorem

If p is prime and gcd(a,p) = 1:

aᵖ⁻¹ ≡ 1 (mod p)

Modular inverse: a⁻¹ ≡ aᵖ⁻² (mod p)

Used everywhere in competitive programming for division under mod.

Where Coprimality Appears

Context	Role
RSA encryption	Key generation uses coprime pairs
CRT (Chinese Remainder Theorem)	Moduli must be pairwise coprime
Hash tables	Table size and step should be coprime
Modular inverse	Exists iff `gcd(a,m) = 1`

Concept Check

Are 35 and 36 coprime?

Interview Tips

Consecutive integers are always coprime: gcd(n, n+1) = 1.
Euler's theorem generalization: aᵠ⁽ⁿ⁾ ≡ 1 (mod n) when gcd(a,n)=1.
CRT: solve simultaneous congruences only when moduli are pairwise coprime.

Base Conversion

Analogy: Different languages for the same number. 10 in decimal = "ten". 1010 in binary = still ten. 0xA in hex = still ten. Same quantity, different symbols.

Positional Number Systems

A number in base b: each digit dₙ has value dₙ × bⁿ.

1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰
       = 8 + 0 + 2 + 1 = 11₁₀

Common Bases

Base	Digits	Prefix	Use Case
Binary (2)	0–1	`0b`	CPU, memory, logic
Octal (8)	0–7	`0o`	Unix permissions
Decimal (10)	0–9	—	Human counting
Hex (16)	0–9, A–F	`0x`	Colors, memory addresses

Live Converter

Number From Base

Algorithm: Any Base → Decimal → Any Base

Step 1: To Decimal

def to_dec(num_str, base):
    val = 0
    for ch in num_str:
        d = int(ch, base)
        val = val * base + d
    return val

Step 2: To Target Base

def from_dec(n, base):
    if n == 0: return "0"
    digits = []
    while n:
        digits.append(
          "0123456789ABCDEF"
          [n % base])
        n //= base
    return ''.join(
      reversed(digits))

Binary ↔ Hex Shortcut

Group binary digits in 4s (right to left). Each group = one hex digit.

1111 0011 0101₂
  F    3    5   = 0xF35

Step-by-Step Dry Run

Converting 42 (decimal) → binary

42 ÷ 2 = 21 remainder 0

21 ÷ 2 = 10 remainder 1

10 ÷ 2 = 5 remainder 0

5 ÷ 2 = 2 remainder 1

2 ÷ 2 = 1 remainder 0

1 ÷ 2 = 0 remainder 1

Read remainders bottom to top: 101010₂

Concept Check

What is 0xFF in decimal?

Interview Tips

Python built-ins: bin(n), oct(n), hex(n), int('FF', 16).
Bit tricks: n & (n-1) clears lowest set bit; n & (-n) isolates it.
Check power of 2: n & (n-1) == 0.
Base-26 encoding commonly appears in Excel column naming problems.

Polynomials

Analogy: A polynomial is a recipe. Each term is an ingredient with a quantity (coefficient) and a "serving size multiplier" (power of x). Evaluating it means: "how much total given x = amount?"

Definition

P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀

Degree highest power with non-zero coefficient

Leading term term with highest degree

Polynomial Evaluator

Enter coefficients (highest degree first, space separated)

Coefficients x =

Horner's Method — O(n)

Rewrite to minimize multiplications: no need to compute x², x³...

P(x) = a₀ + x(a₁ + x(a₂ + x(a₃)))

def horner(coeffs, x):
    # coeffs: [a_n, ..., a_1, a_0]
    result = 0
    for c in coeffs:
        result = result * x + c
    return result

Naive: O(n²) multiplications. Horner: O(n). Same answer, much faster.

Polynomial Operations

Operation	Complexity	Notes
Add / Subtract	O(n)	Add same-degree coefficients
Multiply (naive)	O(n²)	Convolve coefficients
Multiply (FFT)	O(n log n)	Fast Fourier Transform
Evaluate	O(n)	Horner's method
GCD of polynomials	O(n²)	Euclidean algorithm adapted

Polynomial Hashing

Treat a string as a polynomial: each character is a coefficient.

hash("abc") = a×p² + b×p + c  (mod M)

# Rolling hash for substring matching
def poly_hash(s, p=31, m=10**9+7):
    h, pw = 0, 1
    for ch in s:
        h = (h + (ord(ch)-96) * pw) % m
        pw = pw * p % m
    return h

Powers of p and mod prevent collision. Used in Rabin-Karp string matching.

Polynomial Interpolation

Lagrange: Given n+1 points, exactly one degree-n polynomial passes through all of them.

L(x) = Σᵢ yᵢ × ∏ⱼ≠ᵢ (x - xⱼ)/(xᵢ - xⱼ)

Used in: secret sharing, error-correcting codes, numerical integration.

Dry Run — Polynomial Multiplication

(x + 2)(x + 3) = x² + 5x + 6

Coefficients A: [1, 2] → x + 2

Coefficients B: [1, 3] → x + 3

result[0+0] += 1×1 = 1 → x²

result[0+1] += 1×3 = 3 → x¹

result[1+0] += 2×1 = 2 → x¹ (add to 3 → 5)

result[1+1] += 2×3 = 6 → x⁰

Result: [1, 5, 6] = x² + 5x + 6 ✓

Concept Check

Horner eval of [2, -1, 3] at x=2 (i.e. 2x² - x + 3)?

Interview Tips

Polynomial hashing is the foundation of Rabin-Karp and rolling hash problems.
Always apply mod to prevent overflow in hash computations.
Polynomial multiplication = string/array convolution — often solved with FFT in competitive programming.
Lagrange interpolation appears in secret sharing (Shamir's scheme).