Modular Arithmetic for DSA: Rules, Tricks & Examples

Modular arithmetic keeps numbers small while preserving the structure of +, −, ×.

The rules you need:

(a + b) mod m = (a mod m + b mod m) mod m
(a − b) mod m = (a mod m − b mod m + m) mod m     // add m to stay positive
(a × b) mod m = (a mod m × b mod m) mod m

Focus on recognizing:

“Answer can be huge — return it modulo 10^9+7” = apply these rules at every operation

Core Template (Safe Multiply)

Fast power with mod at every step — watch intermediates stay small while the exponent burns down in binary:

Safe Modular Exponentiation

Compute base^exp mod m without overflow.

Fast-power, but reduce mod m after EVERY multiply so intermediates never blow up. Cells show [result, base, exp] at each step. 2^10 mod 1000 = 1024 % 1000 = 24. Keeps numbers bounded by m² throughout. O(log exp).

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        modpow(base, exp, m):
                      
                        2
                          result = 1
                      
                        3
                          while exp > 0:
                      
                        4
                            if exp & 1: result = result * base % m
                      
                        5
                            base = base * base % m
                      
                        6
                            exp >>= 1

The one real trap: (10^9)² overflows 32-bit ints. Widen before multiplying.

static final long MOD = 1_000_000_007L;

public long mul(long a, long b) {
    return a % MOD * (b % MOD) % MOD;   // long math
}

public long add(long a, long b) {
    return ((a % MOD) + (b % MOD)) % MOD;
}

public long sub(long a, long b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

MOD = 1_000_000_007

# Python ints never overflow — just keep % on every step
def mul(a: int, b: int) -> int:
    return a * b % MOD

def sub(a: int, b: int) -> int:
    return (a - b) % MOD   # % already returns non-negative

const long long MOD = 1'000'000'007LL;

long long mul(long long a, long long b) {
    return a % MOD * (b % MOD) % MOD;   // long long math
}

long long add(long long a, long long b) {
    return ((a % MOD) + (b % MOD)) % MOD;
}

long long sub(long long a, long long b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

const MOD = 1_000_000_007n; // BigInt for safety beyond 2^53

function mul(a, b) {
  return (a % MOD) * (b % MOD) % MOD;
}

function sub(a, b) {
  return (((a - b) % MOD) + MOD) % MOD;
}

Rule of thumb: reduce before multiply, reduce after every op.

Pattern 1: Modular Inverse (Division)

a / b mod p doesn’t exist directly. For prime p, the inverse is b^(p−2) mod p (Fermat’s little theorem):

public long inv(long b) {
    return power(b, MOD - 2);   // fast power from next lesson
}

public long div(long a, long b) {
    return mul(a, inv(b));
}

def inv(b: int) -> int:
    return pow(b, MOD - 2, MOD)   # built-in three-arg pow

def div(a: int, b: int) -> int:
    return a * inv(b) % MOD

long long inv(long long b) {
    return power(b, MOD - 2);   // fast power
}

long long div(long long a, long long b) {
    return mul(a, inv(b));
}

function inv(b) {
  return power(b, MOD - 2n); // fast power (BigInt)
}

function div(a, b) {
  return mul(a, inv(b));
}

Division mod p = multiply by b^(p−2).

Common Mistakes

Multiplying two full-size values in int width.

(10^9+6)² ≈ 10^18 — needs 64-bit (long/long long) or Python/BigInt natives.

Negative results after subtraction.

sub(3, 5) must be m − 2, not -2. Add MOD before the final %.

Reducing only once at the end.

Intermediate products explode past 64-bit if you skip per-step reduction. Reduce at every operation.

Complexity

Operation	Time
add/sub/mul	O(1)
inverse	O(log p) via fast power

⚠️ Animation & Content Notice

Modular Arithmetic

Core Template (Safe Multiply)

⚠️ Animation & Content Notice

Safe Modular Exponentiation

Pattern 1: Modular Inverse (Division)

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template (Safe Multiply)

Safe Modular Exponentiation

Pattern 1: Modular Inverse (Division)

Common Mistakes

Complexity

Premium Content

My Private Notes