Math & Number Theory

Review boundary and corrected contracts

Modular power requires nonnegative exponent and positive modulus; initialize 1 % mod so exponent zero modulo one is zero. gcd is normalized nonnegative; lcm handles both zero inputs. Fermat inverse requires a prime modulus and a nonzero residue; floating reciprocal ordering has no universal precision winner.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Memorise four short math routines outright — fast power, sieve, Euclid's GCD, integer binary search — and recognise the problem shapes that call for each.

Series: LeetCode — From Basics to Production-Ready · Session 47 / 65 · Phase 3 · Advanced & specialised

Watch first

Optional original video resources (not prerequisites for the worked examples):

• Binary exponentiation — Errichto Algorithms. Fast power derived rather than recited, including the modular form. If you only watch one thing today, this is it — it is the routine that appears most often.
• The Euclidean algorithm — how and why, visually — Proof of Concept. Why gcd(a, b) = gcd(b, a mod b) is true, shown geometrically. Three lines of code you should be able to justify, not just type.
• Sieve of Eratosthenes — Khan Academy Labs. Short and visual. Watch for where the inner loop starts — at p squared, not at 2p — which is the one detail people get wrong.

Why this session exists

Fast power and the sieve show up often enough to be worth memorising. That is a narrow claim and I want to keep it narrow — this is not a number theory course, and most of number theory does not appear in practice. What does appear is a small set of routines that are each under fifteen lines and each solve a family of problems outright.

There are four. Exponentiation by squaring, because any problem with "compute x^n" or "modulo 10^9+7" needs it and the naive loop is too slow. The sieve of Eratosthenes, because it batches primality work when a full table fits; segmented sieves and individual primality tests serve different memory and query needs. Euclid's algorithm for GCD, because it is three lines and it underpins fraction reduction, LCM, and a surprising number of grid and cycle problems. And binary search on an integer answer, because Sqrt(x) is really a search problem wearing a math costume.

Memorising these is genuinely the right strategy, which is unusual advice in this series. Elsewhere I have pushed derivation over recall, because patterns generalise and memorised solutions do not. Here the routines are small, exact, and unchanging. There is no insight to derive at the whiteboard that you would not simply be re-deriving from the same two lines every time. Learn them, verify you can write them cold, and spend your thinking budget elsewhere.

The meta-skill worth extracting is different: recognising when a problem is secretly a math problem. Happy Number looks like arithmetic and is actually cycle detection. Sqrt looks like math and is actually binary search. Count Primes looks like a loop and is actually a memory-access pattern. Reading past the surface is what this session trains.

Blank-file warm-up

Five minutes, empty file, no notes. Write fast exponentiation by squaring:

1. The iterative form with a while n: loop.
2. The three lines inside: conditional multiply, square the base, halve the exponent.
3. The handling for a negative exponent.

If the loop body comes out in the wrong order — squaring before the conditional multiply — the unchanged loop would compute x^(2n), not x^n, in exact arithmetic. Trace x^3 by hand to check.

Pattern anatomy

There is no single template here. There are four, and each has its own trigger. I will give all four and be explicit about the shape each one answers.

Fast power — the shape is "compute x^n where n is large". The exact-arithmetic invariant: at every step, result × base^n equals the original x^N. The float implementation approximates this identity subject to rounding. Halving n and squaring base preserves that product, and peeling off a factor when n is odd keeps it exact.

def fast_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:            # odd exponent: peel one factor into the result
            result *= x
        x *= x               # square the base
        n >>= 1              # halve the exponent
    return result
 
def pow_mod(base: int, exp: int, mod: int) -> int:
    """Same routine under a modulus — the version you actually need more often."""
    if exp < 0 or mod <= 0:
        raise ValueError("nonnegative exponent and positive modulus required")
    result = 1 % mod
    base %= mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

Sieve of Eratosthenes — the shape is "how many primes below n" or "give me all primes below n". The invariant: when the outer loop reaches p, every composite with a prime factor smaller than p has already been marked, so if p is still unmarked it is prime.

def count_primes(n: int) -> int:
    if n < 3:
        return 0
    is_prime = bytearray([1]) * n
    is_prime[0] = is_prime[1] = 0
    p = 2
    while p * p < n:
        if is_prime[p]:
            # start at p*p: smaller multiples already marked by smaller primes
            is_prime[p * p : n : p] = bytearray(len(range(p * p, n, p)))
        p += 1
    return sum(is_prime)

Two optimisations are load-bearing rather than decorative. Starting the inner marking at p * p rather than 2p is correct because any multiple kp with k < p has a prime factor below p and was already struck. Stopping the outer loop at p * p >= n is correct because a composite below n must have a factor at most its square root.

Euclid's GCD — the shape is any question about common divisors, fraction reduction, or periodicity.

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
 
def lcm(a: int, b: int) -> int:
    return 0 if not a or not b else abs(a // gcd(a, b) * b)        # divide first: reduces intermediate size; final product may still overflow

Integer binary search — for nonnegative integer x, find the largest k with k² ≤ x. Values below lo are known feasible; values above hi (within the initial range) are known infeasible. On exit lo = hi+1, so hi is the last feasible value. Negative x is outside this routine's contract.

def my_sqrt(x: int) -> int:
    lo, hi = 0, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            lo = mid + 1          # mid is feasible; look higher
        else:
            hi = mid - 1
    return hi                     # hi ends at the largest feasible value

Newton iteration for integer square root uses r = (r + x // r) // 2. Handle x = 0 separately, start above the root (for example r = x for positive x), and stop when the next estimate is not smaller. Starting at zero would divide by zero. Binary search transfers to any monotone predicate; Newton requires an appropriate mathematical update and convergence argument, and also applies to roots of functions beyond square roots.

The cue

You are looking at a math problem when the statement contains these tells:

1. "Modulo 10^9 + 7" — this is a counting problem whose answer overflows, and somewhere in it you will need modular arithmetic and quite possibly modular exponentiation. The specific constant is a large prime, which guarantees an inverse for every nonzero residue, but never for zero.
2. "Compute x^n" with n up to 10^9 or beyond. Naive multiplication is O(n) and hopeless. Fast power is O(log n) and mandatory.
3. "Primes below n" with n up to 10^6 or 10^7. Sieve. Trial division per number is O(n·sqrt(n)) and will not finish.
4. Fractions, ratios, "reduce to lowest terms", or anything about repeating cycles. GCD, almost always.
5. "Without using the built-in function" — sqrt, pow, division. The problem is asking you to reimplement a primitive, and the intended method is binary search or bit-shifting.
6. A digit-manipulation loop that might not terminate — sum of squared digits, digital roots. If a process can cycle, the answer involves cycle detection rather than arithmetic.

For sums and products whose result is required modulo m, reduce intermediate results to control integer size. Do not blindly reduce quantities used for comparisons, integer division or ordering: those operations are not preserved by taking residues. In fixed-width languages, even two already-reduced residues can have a product too large for the type; widen it or use overflow-safe modular multiplication.

Guided solve

Pow(x, n) — implement pow(x, n) computing x raised to the power n, where n can be negative and as large as 2^31 in magnitude.

Naive first, and name why it fails. Multiplying x by itself n times is O(n). With n around two billion that is two billion multiplications and it will not complete. So you need something logarithmic, and the route to logarithmic is halving.

The observation is that x^n can be built from x^(n/2). If n is even, x^n = (x^(n/2))^2 — one squaring instead of n/2 multiplications. If n is odd, x^n = x · (x^((n-1)/2))^2. Each step halves the exponent, so there are floor(log2(|n|)) + 1 steps for nonzero n, up to 32 when the original signed exponent is −2^31, whose positive magnitude is 2^31.

The iterative form reverses this into a sweep over the bits of n. Think of it as: n in binary tells you which powers x^1, x^2, x^4, x^8, ... to multiply together. Bit i of n set means include x^(2^i). The loop maintains x as the current x^(2^i), squaring it each iteration to advance i, and multiplies it into the result whenever the corresponding bit is set.

Trace x = 2, n = 10. Binary 10 is 1010, so the answer is 2^2 × 2^8 = 4 × 256 = 1024. The loop: n=10 even, square x to 4, n becomes 5. n=5 odd, result = 4, square x to 16, n becomes 2. n=2 even, square x to 256, n becomes 1. n=1 odd, result = 4 × 256 = 1024, n becomes 0. Loop ends. Correct.

Now the edge cases, which is where this problem actually gets you:

Negative exponent. x^(-n) = 1 / x^n. Handle it by inverting x and negating n at the top, which is what the template does. The alternative — computing the positive power and inverting at the end — is algebraically equivalent, but rounding and overflow can differ; neither order is universally more accurate.

n = -2^31. Negating it overflows a 32-bit signed integer in Java or C++, since 2^31 is not representable. Python is immune because its integers are unbounded, but a reviewer may well ask, and the answer is to widen to a 64-bit type before negating.

x = 0 with negative n. Division by zero. The problem constraints usually exclude it; check and say so rather than silently assuming.

Floating-point accumulation. Powers of two such as fast_pow(2.0, 10) are exactly representable and return exactly 1024.0 here. Other bases, for example 0.1, need not be exactly representable, and each multiplication can round; compare to a reference with a stated tolerance. Underflow and overflow also matter for extreme inputs. Modular integer arithmetic avoids rounding, but not growing-integer operation costs.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Sqrt(x) — integer square root, no built-in. Binary search on the answer. The trap is the return value: decide before you code whether you return lo, hi, or mid, and justify it from the loop invariant.
• Count Primes — sieve. Get both optimisations right: inner loop starts at p*p, outer loop stops at p*p >= n.
• Happy Number — repeatedly replace the number by the sum of the squares of its digits; decide whether it reaches 1. This is cycle detection. Floyd's tortoise and hare gives O(1) space; a seen-set gives O(k) space and is easier to write.

If those land early, do Excel Sheet Column Title — base conversion with a one-indexed alphabet, which is a small but genuinely fiddly off-by-one exercise.

Common failure modes

Squaring before the conditional multiply. The order inside the fast-power loop matters: test the bit and multiply into the result first, then square the base. With the rest of this loop unchanged, moving the square before the multiply computes x^(2n) in exact arithmetic. Trace x^1 — it should return x and a reversed loop returns x^2.

Sieve inner loop starting at 2p. Not wrong, just wasteful — it re-marks composites already struck by smaller primes. On n = 10^6 the difference is measurable. Start at p*p.

Sieve outer loop running to n instead of to sqrt(n). Also not wrong, also wasteful. Once p exceeds the square root, every remaining unmarked number is prime and there is nothing left to mark.

Off-by-one on the binary search return. With the lo <= hi loop form, hi ends at the largest value satisfying the predicate and lo at the smallest violating it. Know which one you want. Test with x = 8, where the answer is 2, and x = 1, where it is 1.

Overflow before the modulo. Reducing each multiplication controls magnitude but does not make the product itself safe in a fixed-width type. For a modulus near 10^9+7, two residues can require roughly 60 product bits. Python computes that product exactly; in other languages use a sufficiently wide or overflow-safe multiplication routine. Signed C++ overflow is not a defined wrapping operation.

Assuming % on negatives matches other languages. Python's % returns a result with the sign of the divisor, so -7 % 3 is 2, while C and Java give -1. If you are translating a solution across languages, this bites.

Myth: Checking whether n is prime requires testing divisibility by every number up to n, or at least by every prime up to n.

Why: You only need to test divisors up to the square root of n. If n = a·b with both factors exceeding sqrt(n), their product would exceed n, which is a contradiction — so at least one factor is at most sqrt(n). That takes a primality test from O(n) to O(sqrt(n)). And when you need many primes rather than one test, the sieve is better still: it does no division at all, only marking, and produces every prime below n in O(n log log n) total. The instinct to test each number individually is what makes people write an O(n·sqrt(n)) Count Primes that times out.

Steps 1: Because exponentiation is repeated multiplication and multiplication is associative, x^n can be regrouped freely.

Steps 2: Because n can be written in binary as a sum of distinct powers of two, x^n is the product of x^(2^i) over exactly the bit positions i where n has a 1.

Steps 3: Because each x^(2^i) is the square of the previous one, all of them can be generated by repeated squaring in one pass.

Steps 4: Because a 32-bit exponent has at most 32 bits, that pass runs at most 32 times regardless of how large n is.

Steps 5: Because each iteration does a constant number of multiplications, the total cost is O(log n) rather than O(n).

Steps 6: For exponent 10^9 the binary loop takes 30 iterations instead of a billion repeated multiplications. That is an exact iteration count; elapsed time also depends on the modulus size and runtime, and no benchmark is claimed.

Picture: To climb a thousand steps you do not take a thousand single steps. You take one step, then a two-step, then a four-step, doubling each time, and you pick exactly the jump sizes whose binary digits spell out one thousand. Ten jumps instead of a thousand steps.

Trigger: Fires whenever a quantity is built by repeating an associative operation a large number of times — powers, matrix powers, repeated function application.

Name: Sieve of Eratosthenes

The sieve marks multiples of each surviving prime in strides. Its classical arithmetic-operation bound is O(n log log n) and its byte-array storage is O(n); that is not one sequential sweep.

Cost: O(n) memory — at n = 10^9 a byte array is a gigabyte and infeasible; pointless overhead if you only need to test one number

Name: Trial division to sqrt(n)

Gain: O(1) word storage and O(sqrt(n)) trial divisions per test; useful at modest bounds, but not practical for arbitrarily huge n

Cost: Testing every number below n costs O(n·sqrt(n)) in total, which is far worse than the sieve when you need many primes

Pick: Sieve when you need all primes below a bound and that bound is at most about 10^7, so the byte array fits comfortably in memory. Trial division when you need to test a small number of individual values, or when n is large enough that an O(n) array is out of the question.

Worked variant — modular fast power, annotated

The plain pow(x, n) is the memorisable core, but the version that actually appears is the modular one, because combinatorics problems ask for answers "modulo 10^9 + 7". Write it once with the reasoning attached.

MOD = 10**9 + 7
 
def power_mod(x: int, n: int, mod: int = MOD) -> int:
    """x^n mod m in O(log n) multiplications."""
    if n < 0 or mod <= 0:
        raise ValueError("nonnegative exponent and positive modulus required")
    x %= mod                       # shrink the base FIRST; keeps every
    result = 1 % mod               #   later product bounded by mod^2
    while n > 0:
        if n & 1:                  # this binary digit of n is set,
            result = result * x % mod   # so fold the current square in
        x = x * x % mod            # advance to the next square: x^(2^k)
        n >>= 1                    # consume the digit
    return result
 
def mod_inverse(a: int, mod: int = MOD) -> int:
    """Division under a PRIME modulus. Fermat's little theorem:
       a^(m-1) = 1 (mod m), so a^(m-2) is a's multiplicative inverse.
       Requires mod to be prime and a not divisible by mod."""
    return power_mod(a, mod - 2, mod)
 
assert power_mod(2, 10) == 1024
assert 6 * mod_inverse(3) % MOD == 2      # 6 / 3 = 2, under the modulus

Three things to be able to say about this code.

Why it is O(log n). n >>= 1 halves the exponent every iteration, so the loop runs once per binary digit of n. The algorithm is really "write n in binary and multiply together the squares corresponding to set bits" — x^13 = x^8 · x^4 · x^1 because 13 is 1101.

Why x %= mod comes first. It limits the base to a residue before any squaring, so each later product is less than mod². This bounds Python integer sizes, but mod² must still fit any fixed-width product type used in a port. Reduction after overflow cannot restore lost information.

Why modular division needs an inverse. To divide a by b modulo m, multiply a by an inverse of b; ordinary / is not the operation. An inverse exists exactly when gcd(b,m) = 1. For prime m and nonzero b modulo m, Fermat gives b^(m−2) as that inverse. The helper above assumes this contract; it does not validate primality or reject a zero residue. For example, using b = 0 does not produce a valid inverse.

Memory hook — "square the base, read the bits"

For fast power: square the base, read the bits. Consume the current bit first, multiplying the current x into result when needed; only then square x and shift n. Other correct formulations exist, but this order matches the invariant of the displayed loop.

For the sieve: "start at p squared, step by p." Every composite below p*p already has a smaller prime factor and has therefore already been struck out, so beginning the inner loop at 2*p is pure wasted work. And the outer loop stops at sqrt(n), because a composite n must have a factor at or below its square root.

For Euclid: "swap and mod until zero." gcd(a, b) = gcd(b, a % b), terminating when b hits zero, at which point a is the answer. For nonzero a and b, LCM is abs(a // gcd(a, b) * b); if either is zero, return zero before division. Divide before multiplying to reduce the intermediate size, not to guarantee the final product fits a fixed-width type.

For integer binary search: "search the answer, not the array." Sqrt(x), or any "smallest value satisfying a monotone predicate", is a binary search over the answer range with no array in sight.

What reviewers actually ask

These are rarely the main question. They appear as a required subroutine, or as a warm-up, and fumbling one reads badly precisely because it is meant to be quick.

• 50 · Pow(x, n) (Medium) — Practice selection. Probing exponentiation by squaring. Follow-up: "n can be negative" — compute the positive power and take the reciprocal; watch the -2^31 edge case where negation overflows in fixed-width languages.
• 204 · Count Primes (Medium) — Practice selection. Probing the sieve, specifically the p*p start. Follow-up: "what is the actual complexity?" — O(n log log n), and you should be able to say roughly why.
• 69 · Sqrt(x) (Easy) — Practice selection. Probing that you see a search rather than a formula. Follow-up: "now do it without overflow" — handle mid == 0 as feasible, otherwise compare mid <= x // mid; also compute the midpoint without an overflowing sum.
• 1071 · Greatest Common Divisor of Strings (Easy) — Practice selection. Probing whether you recognise Euclid outside of numbers; first require a + b == b + a; only then is the answer prefix length gcd(len(a), len(b)) (for nonempty inputs).
• 202 · Happy Number (Easy) — Practice selection. Probing that you see a cycle, not arithmetic — Floyd's tortoise and hare applies directly.
• 7 · Reverse Integer (Medium) — Practice selection. Probing overflow discipline. Python hides the problem, so state the 32-bit check explicitly anyway.
• 172 · Factorial Trailing Zeroes (Medium) — Practice selection. Probing that trailing zeros count factors of 5, since factors of 2 are always more plentiful.

For Trailing Zeroes, each zero in n! needs a factor 2 paired with a factor 5. Twos are more abundant, so count fives: n // 5 + n // 25 + n // 125 + ..., stopping when the divisor exceeds n. Multiples of 25 supply the second five, multiples of 125 the third, and so on; for n = 25 the total is 5 + 1 = 6.

The escalation to watch is a requested modular result. Reduce the algebraic sums and products, not quantities needed for ordering. Modular division needs an invertible denominator; a prime modulus still excludes the zero residue.

Complexity

Fast power: O(log(1 + |n|)) arithmetic operations and O(1) numeric variables in the iterative form. For nonzero magnitude the loop runs its bit_length times: at most 31 for positive signed-32-bit n, but 32 for n = −2^31 after negation. Exponent zero takes zero iterations. Python big-integer modular products have costs depending on modulus bit length; O(1) variables is not O(1) bits.

Sieve: O(n log log n) time, O(n) space. The time bound comes from summing n/p over all primes p below n, and the sum of prime reciprocals grows like log log n. That is close enough to linear that you can treat it as linear for estimation. Space is one byte per candidate with a bytearray, so n = 10^7 is ten megabytes — fine. A bitset would be eight times smaller if you need it.

GCD: O(log(1 + min(|a|, |b|))) remainder steps for positive magnitudes, with constant work for zero inputs. The smaller argument shrinks by at least half within two steps. Arbitrary-precision division costs depend on operand sizes, so this is not a bit-complexity bound.

Integer binary search: O(log(1 + x)) iterations for nonnegative x, including O(1) work at zero. Python midpoint multiplication is exact, but its bit cost grows with x.

Self-check (answer follows each question).

Q: In the fast-power loop, why must the conditional multiply come before the squaring?

A: The base variable holds x^(2^i) for the bit position currently being examined. Squaring first advances it to the next power before the current bit has consumed it, producing an answer that is off by one squaring. Trace x^1 to see it.

Q: Why does the sieve's inner marking loop start at p*p rather than 2p?

A: Any multiple k*p with k < p has a prime factor smaller than p, so it was already marked when that smaller prime was processed. Starting at p*p skips all of that redundant work.

Q: Why can the sieve's outer loop stop once p*p >= n?

A: Every composite below n has at least one prime factor at most its square root. Once p exceeds sqrt(n), no unmarked number below n can still be composite, so there is nothing left to mark.

Q: What does the constant 10^9 + 7 signal when you see it in a problem?

A: The result is required modulo that prime. Reduce sums and products as needed, while keeping exact values for comparisons or integer division. Division modulo the prime requires a nonzero denominator residue and its inverse; a zero residue is not invertible.

Q: Write Euclid's GCD and state why it terminates.

A: First normalize a, b = abs(a), abs(b), then repeat a, b = b, a % b while b is nonzero, and return a. With nonnegative operands the new remainder lies in [0, b), so the second argument strictly decreases. The convention gives gcd(0,0) = 0.

Q: Happy Number is in a math problem set but is not really arithmetic. What is it, and what is the O(1)-space solution?

A: It is iteration of the digit-square-sum function. On positive integers the trajectory eventually stays in a finite range, so both happy and unhappy inputs cycle. Floyd's one-step/two-step pointers eventually meet; return happy only if their meeting value is 1, the fixed point. Merely detecting a cycle is not enough (2 is an unhappy example). The algorithm uses O(1) stored states, versus a set of visited values.

Stretch: true

You can now…

• Write iterative exponentiation by squaring cold, and explain the O(log n) bound via the binary digits of the exponent.

• Write the modular variant, reducing the base before the loop, and name why that matters in fixed-width languages.

• Perform modular division with a Fermat inverse only for a prime modulus and a nonzero denominator residue.

• Write the sieve with the inner loop starting at p squared and the outer loop stopping at sqrt(n), and justify both bounds.

• Write Euclid's GCD in three lines and derive LCM from it, dividing before multiplying.

• Recognise Sqrt(x) as binary search over an answer range and avoid overflow by comparing with division.

• Spot problems wearing a math costume — Happy Number as cycle detection, trailing zeroes as counting factors of five.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

These four routines are the rare case where pure recall is the goal. If any of them takes more than three minutes to write cold, it belongs at failed regardless of whether you eventually produced it.

• Four routines are worth outright memorisation: fast power, sieve, Euclid's GCD, integer binary search.

• Fast power sweeps the bits of the exponent: multiply into the result when the bit is set, then square the base. Order matters.

• The sieve's two optimisations are load-bearing — inner loop starts at p*p, outer loop stops at p*p >= n.

• A requested modular result permits reduction of sums and products; comparisons and integer division need separate reasoning, and inverses require nonzero residues under a prime modulus.

• Sqrt(x) is binary search on a monotone predicate, not a math problem. So is 'largest k such that f(k) holds' in general.

• Trial division to sqrt(n) for a single primality test; sieve when you need every prime below a bound under about 10^7.

Corrective source notes

• Binary Exponentiation - Algorithms for Competitive Programming — Binary exponentiation needs associative multiplication and uses logarithmically many multiplications. Checked 2026-10-07.

• Sieve of Eratosthenes - Algorithms for Competitive Programming — Sieve marking may begin at p squared because smaller composites have an already considered factor. Checked 2026-10-07.

• Euclidean algorithm for computing the greatest common divisor - Algorithms for Competitive Programming — LCM can be computed using GCD; zero/sign conventions must be supplied by the implementation. Checked 2026-10-07.

• Built-in Types — Python 3.14.8 documentation — Python integer bitwise operations behave with infinite sign extension, so negative right shifts do not truncate to zero. Checked 2026-10-07.

• Python 3.14 floating-point tutorial — binary representation and rounding limitations; integer semantics — sign-extending shifts. Freshly checked 2026-10-09.

• Modular inverse — inverse existence requires coprimality; the Fermat exponent applies under a prime modulus with a nonzero residue. Freshly checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.