Even Odd Modulo

Modular arithmetic keeps numbers bounded: (a+b)%m, (a*b)%m, and nested % respect congruence—the language of remainders.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Replace x with x mod m after each op to prevent overflow. Congruence transformations let you add/subtract multiples of m freely on both sides.

Try this in Python

def mod_pow(base: int, exp: int, mod: int) -> int:
    res = 1
    base %= mod
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res


print(mod_pow(2, 1000000000, 1000000007))

Common mistakes

• Applying mod only at the end on sums/products.
• Negative remainders in Python (-1 % 5 == 4 is fine, but watch C++).
• Dividing without modular inverse.

Key takeaways

• Use Python’s % for nonnegative canonical residues.
• Expand (a-b)%m as (a-b+m)%m when needed.