Math, number theory, and combinatorics · HTML
If a≡b (mod M), addition and multiplication preserve congruence; binary exponentiation multiplies powers base^(2^k) selected by exponent bits.
Recognition signals
- The answer is requested modulo M
- The exponent is enormous
- Modular inverses or combinations appear
- Intermediate products would explode
- Only residue classes need to be retained
False friends
| Signal | Why it is different |
|---|
| Exact quotient or magnitude comparison | Reduction loses scale and cannot recover original ordering. |
| Using Fermat inverses unconditionally | a^(M-2) needs prime M and nonzero a modulo M. |
Core invariant
During binary power, result*base^exp remains congruent to the original target; each step consumes one bit.
State, transition, and processing order
| Item | Definition |
|---|
| State | result, current base, remaining exponent, and modulus. |
| Transition | If the low bit is one, multiply base into result; square base modulo M and halve the exponent. |
| Frontier / order | Unprocessed high exponent bits form the frontier; each iteration removes the lowest bit. |
Python skeleton
def mod_pow(base, exp, mod):
if mod <= 0 or exp < 0:
raise ValueError
result = 1 % mod
base %= mod
while exp:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def prime_mod_inverse(a, p):
if a % p == 0: raise ZeroDivisionError
return mod_pow(a, p-2, p)
Correctness sketch
- A nonnegative exponent is a sum of selected powers of two.
- When its low bit is one, current base is exactly the corresponding power.
- Squaring and shifting preserve the result*base^exp invariant.
- At exp=0, result is the target power modulo M.
Complexity
| Time | Space | Parameters |
|---|
| O(log exp) | O(1) | nonnegative exp and positive modulus mod |
Edge cases
- exp=0 returns 1 mod M
- mod=1 returns zero
- Normalize a negative base
- An inverse requires gcd(a,M)=1
- Fixed-width multiplication may overflow before reduction
Error patterns
| Pattern | Why it fails / fix |
|---|
| Reducing only at the end | Intermediates become huge or overflow. |
| Ignoring inverse preconditions | A nonunit has no modular inverse. |
| Taking division modulo M directly | Modular division means multiplying by an existing inverse. |
Selection and exclusion rules
- Huge exponent: binary exponentiation.
- Additive/multiplicative counting: reduce during every transition.
- Prime modulus and nonzero denominator: Fermat inverse is available.
- Composite modulus: use extended Euclid and test coprimality.
Original micro-example
| Part | Detail |
|---|
| Result | The result is 5. |
| Scenario | Compute 3^13 mod 7. |
| Walkthrough | 13 is binary 1101; multiply only selected repeated squares and reduce at every step. |
Recall prompts
My notes