Modular arithmetic

Modular arithmetic is the arithmetic of remainders: you fix a modulus $m$ and track only what a number leaves behind on division by $m$, working inside the finite ring $\mathbb{Z}/m\mathbb{Z} = \{0, 1, \dots, m-1\}$ instead of on the full integers. As a domain it is less a topic than a lens — an enormous share of the archive poses a question that, read carefully, depends only on a residue, even when the word "modulo" never appears. The skill this page is about is recognising that a problem lives here: once you see that the quantity asked for is a remainder, an astronomically large computation collapses to one that never leaves $[0, m)$. The mechanics that follow from that — fast exponentiation, the modular inverse, the Chinese Remainder Theorem, the overflow trap — are the subject of the deeper Modular Arithmetic note; here I want to catalogue the disguises the domain wears, so you learn to spot it, and the few facts about the modulus that decide what you are allowed to do once you have.

The one property, in one line

The reason any of this works is that congruence — $a \equiv b \pmod m$, meaning $m$ divides $a - b$ — is preserved by addition, subtraction, and multiplication. So

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m,$$

and likewise for $a - b$ and $a \times b$. You may therefore reduce after every step and never let an intermediate value grow. Every disguise below is ultimately a chance to apply that one closure property early instead of late. Note what is missing from the list: division. Whether you may divide depends on the modulus, and that is the subject of the section after the disguises.

The disguises

"The last $k$ digits of …" is the tell that gives the game away most directly: the last $k$ decimal digits of $N$ are exactly $N \bmod 10^k$. Problem 97 wants the final ten digits of $28433 \times 2^{7830457} + 1$, a number with over two million digits; working modulo $10^{10}$ throughout, nothing bigger than $10^{20}$ is ever formed. Problem 48 (public, solutions/public/p0048/) sums $1^1 + 2^2 + \dots + 1000^{1000}$ and asks the same "last ten digits", and the private problem 104 (Fibonacci terminal digits) is the same instinct dressed differently. Problem 778 takes the idea to the limit. Its carry-free "freshman's product" multiplies numbers digit by digit, keeping each column's product mod $10$. With no carries, every decimal place is its own copy of $\mathbb{Z}/10\mathbb{Z}$. One column is a ten-entry histogram of digits, and combining $R$ factors is a convolution of histograms under multiplication mod $10$. That convolution can be raised to the $R$th power by squaring. Problem 990 puts the carries back. It counts addition equations $x_1 + \dots + x_k = y_1 + \dots + y_m$ of bounded length, with terms of up to $24$ digits, so no table keyed by value can work. Check the equation the way it is done on paper. In each column the left digits, minus the right digits, plus the incoming carry, must be $\equiv 0 \pmod{10}$, and the quotient is the signed carry into the next column. The equation holds exactly when the terms run out with carry $0$. So a digit DP needs only the carry and how many terms are still active, and the values never appear. Writing each right-hand digit as $9 - d'$ turns the subtraction into an addition, so both sides draw from the same digit distributions.

"Is this divisible by …?" is a residue-is-zero question. Problem 78 (public, solutions/public/p0078/) asks for the first $n$ whose partition count $p(n)$ is divisible by one million — and because only divisibility matters, the whole dynamic programming table can be carried mod $10^6$, so the values that in truth run to hundreds of digits stay in a machine word:

partition_value += (-1) ** (k - 1) * partitions[n - pent_k1]
# ... accumulate the pentagonal recurrence ...
partition_value %= divisor          # only the residue matters, so reduce and store that
partitions.append(partition_value)

The private problems 129 and 132 (when does a repunit become divisible by $n$?) and the "unlucky prime" divisibility tests of the later archive are the same shape. Problem 274 runs the idea backwards: it asks for the multiplier $m$ that makes the schoolbook divisibility rule "drop the last digit $b$, add $b \cdot m$" exact for a prime $p$. Writing $n = 10a + b$ gives $10 f(n) = n + b(10m - 1)$, so the rule works precisely when $10m \equiv 1 \pmod p$ — every such divisibility trick is a modular inverse of $10$ in disguise, and this one even has a closed form that depends only on the last digit of $p$. Problem 706 asks about divisibility of every substring at once. A substring is divisible by $3$ exactly when the digit prefix sums at its two ends agree mod $3$, so $f(n)$ is $\sum_r \binom{c_r}{2}$ over the counts $c_r$ of prefixes with each residue. The problem only asks whether $f(n)$ is itself divisible by $3$, so the counts can be kept mod $3$ too. That leaves $81$ states for a transfer matrix, raised to the $10^5$th power by squaring. Residues are being taken twice here: once of the digit sums and once of the counts. Problem 303 makes the residue the state of a search. It wants, for each $n \le 10^4$, the least multiple of $n$ written with the digits $0$, $1$, $2$ only, and for some $n$ that multiple runs to twenty digits. Appending a digit $d$ sends the remainder $r$ to $(10r + d) \bmod n$, so two prefixes with the same remainder behave identically from then on and only the smaller is worth extending. The candidates collapse to a graph on $n$ remainders. A breadth-first search that tries digits in ascending order reaches remainder $0$ first along the smallest numeral. Pigeonhole on the repunits guarantees that a path to $0$ exists. Problem 294 asks a divisibility-and-digit-sum question about strings of $11^{12}$ digits, too long even to walk one digit at a time. A digit block's residue depends on where it sits: a block placed above $L$ lower digits contributes its own residue times $10^L$. So each block's table of (residue mod $23$, digit sum) counts is measured from the block's own lowest digit, and is multiplied by $10^L \bmod 23$ only at the moment two blocks are joined. Joining is then an associative product of small tables. A length of $3 \times 10^{12}$ is reached by squaring in about forty doublings. Because $10$ is a unit modulo the prime $23$, that multiplication only permutes the residues and never merges two of them.

"Give the answer modulo $1\,000\,000\,007$." Counting problems whose true answer overflows any integer type hand you the modulus explicitly — the residue is the deliverable. Here the domain is not a shortcut you discover but a contract you are handed: every count, product, and binomial coefficient is computed in the ring from the start. This is the register a large fraction of the combinatorial problems past 300 are written in — and, as the section after the disguises shows, the kind of modulus you are handed matters. The contract can even be attached to a question that looks real-valued. Problem 721 wants $\lfloor(\lceil\sqrt a\rceil + \sqrt a)^{a^2}\rfloor$. Its conjugate $\lceil\sqrt a\rceil - \sqrt a$ lies in $[0, 1)$, so the floor is the integer $x^n + y^n$ minus one. That integer is computed in the ring $\mathbb{Z}_p[\sqrt a]$, whose elements are pairs of residues, and no real number ever appears. Problem 479 attaches it to complex numbers. It sums powers of $(a+b)(b+c)(c+a)$ over the three roots of a cubic whose coefficients depend on $k$, and two of those roots can be complex. The product is symmetric in the roots, so Vieta's formulas rewrite it in the coefficients alone, and it comes out as an integer polynomial in $k$. No root is ever found, and each $k$ contributes a plain geometric series in the ring. Problem 517 is a recursion on a real argument, $g_a(x) = g_a(x-1) + g_a(x-a)$ with $a = \sqrt n$. Unrolled, it counts lattice paths and telescopes to a sum of binomials $\binom{\lfloor x - ja \rfloor + j}{j}$, taken mod the prime from factorial tables. The real number survives only inside that floor, and an integer square root of $j^2 n$ computes it exactly, so floating point never touches the residue. Sometimes no extension ring is needed at all. Problem 1007 reaches a signed sum of Fibonacci numbers, and Binet's formula would turn it into two geometric series if only $\sqrt 5$ were available. Modulo its prime $10^9 + 9 \equiv 4 \pmod 5$, $5$ is a quadratic residue. So $\sqrt 5$ and the golden ratio are ordinary elements of $\mathbb{F}_p$, and the real-number identity holds there word for word. Before you build $\mathbb{Z}_p[\sqrt d]$, ask whether $d$ already has a square root mod $p$.

"… modulo $n + 1$" written into the definition. A modulus that is part of the object, rather than of the deliverable, is often there to simplify it. Problem 512 defines $f(n) = \sum_{i=1}^{n} \varphi(n^i) \bmod (n + 1)$. Modulo $n + 1$ we have $n \equiv -1$, and $\varphi(n^i) = n^{i-1}\varphi(n)$, so the terms alternate in sign and cancel in pairs. That leaves $\varphi(n)$ for odd $n$ and $0$ for even $n$. Substitute the residue of the base before you compute anything.

"The fractional part of $a/n$." A fractional part is a residue divided by $n$: $\{a/n\} = (a \bmod n)/n$. Problem 850 sums $\{i^k/n\}$ over $i$, and this turns it into a sum of residues of $i^k$. For odd $k$, $i \mapsto n - i$ sends $i^k$ to $-i^k$, so every non-zero residue pairs with its negative and each pair contributes exactly $n$. Only the residues that are $0$ escape the pairing. The sum becomes $(n - z)/2$, where $z$ counts the $i$ with $n \mid i^k$, and $z$ is a question about each prime power of $n$ separately. A sum of residues over a symmetric set is often a count of the residues that are fixed by the symmetry.

"How many of these sum to a multiple of $m$?" When the question counts objects by the residue of a total, put the residue in the exponent. Problem 250 counts the subsets of $\{1^1, 2^2, \dots, 250250^{250250}\}$ whose sum is divisible by $250$ — out of $2^{250250}$ subsets. Each element matters only through $k^k \bmod 250$, so a quarter-million elements become a census over $250$ residues, and the subset-sum generating function $\prod_k (1 + x^{k^k})$ is computed not in $\mathbb{Z}[x]$ but in $\mathbb{Z}[x]/(x^{250} - 1)$, where $x^{250} = 1$ makes exponents add modulo $250$ by themselves: the state is $250$ counters, never a polynomial of growing degree. The smallest instance of the same trick is parity — problem 996 keeps only the even-total terms of a generating function as $\tfrac12\big(f(y) + f(-y)\big)$, the root-of-unity filter for modulus $2$. The parity filtered can be the count of one kind of element. Problem 976 analyses a game and finds that the winner depends on whether the number of strips of length $3 \bmod 4$ is even. The multiset generating function gives each class its own factor, so that parity is filtered by averaging only the $3 \bmod 4$ factor over $x \mapsto \pm x$: $\tfrac12\big[(1-x)^{-c} + (1+x)^{-c}\big]$. The filter is cheapest when the modulus is prime. Problem 635 counts the $p$-element subsets of $\{1, \dots, qp\}$ whose sum is divisible by $p$. Averaging over the $p$th roots of unity $\omega^j$, every $j \ne 0$ gives a primitive root again, so $k \mapsto \omega^{jk}$ visits each root exactly $q$ times and all $p - 1$ non-trivial terms are equal. Each is read off from $\prod_r (1 + rt) = 1 + t^p$. The filter collapses to one binomial coefficient plus a correction, divided by $p$.

The total can also be a function of $n$ rather than of a chosen subset. Problem 967 counts the $n \le 10^{18}$ whose distinct prime factors up to $120$ have a sum $S(n)$ divisible by $3$. Give each $n$ the value $x^{S(n)}$ in $\mathbb{Z}[x]/(x^3 - 1)$. Over coprime factors the sums add, so this is a multiplicative function, and the Dirichlet machinery runs on triples of exact counts, with no complex root of unity in sight. Divisibility by a fixed set of primes is itself periodic, so the small primes' share of $S(n)$ depends only on $n$ modulo their product, and one prefix table stands in for all of them. The Modular Arithmetic note has the split.

The residue being counted can be a whole vector. In problem 619 a product is a perfect square when every prime exponent in it is even, so a number matters only through its exponents mod $2$. That is a vector over the field $\mathbb{F}_2$, and multiplying numbers adds their vectors. A square-product subset is a subset whose vectors sum to zero, which makes the count linear algebra: $2^{n-r} - 1$ for $n$ vectors of rank $r$. The vectors have one coordinate per prime up to $1.2 \times 10^6$, but a prime above $\sqrt b$ divides each number at most once. Each such prime can be pivoted out at the cost of exactly one unit of rank, so Gaussian elimination runs over only the $186$ small primes.

Periodicity and cyclic structure. Residues wrap around, so any process defined by "$+$" or "$\times$ a constant" is eventually periodic modulo $m$, and the period is often the real question. Problem 19 (public, solutions/public/p0019/) is a calendar: the day of the week is a residue mod 7, so counting how often the first of a month is a Sunday is arithmetic mod 7, no date library needed. Pisano periods (the cycle length of Fibonacci numbers mod $m$, problem 854), the multiplicative order of an element, and "clock"-flavoured problems (506, 790, 891) all turn on the same idea: find the cycle, then jump across billions of steps by reducing the step count modulo its length. The cycle can also sit in the index rather than in the values. In problem 506 the digit stream repeats every $6$ digits and sums to $15$ per period. Terms $15$ apart therefore start at the same phase, so $v_{n+15} = 10^6 v_n + Q_{n \bmod 15}$. Each residue class of $n$ mod $15$ is then a geometric series, and $10^{14}$ terms cost fifteen exponentiations. The period is often provable rather than merely observed: in problem 250 the map $k \mapsto k^k \bmod 250$ repeats every $500$ values of $k$ (for $k \ge 3$), because $250 = 2 \cdot 5^3$ and the Carmichael function gives $\lambda(125) = 100$, so a shift by $500$ leaves base and exponent alike unchanged modulo each factor — a quarter-million exponentiations become one block of five hundred. Where no theorem hands you the period, detect it: problem 943 walks deterministic sequences of parity masks only until one repeats, then answers "the first $k$ terms" by counting whole periods. Even without a period, a step of the form $x \mapsto ax + c \pmod m$ can be jumped. Affine maps compose into affine maps, so $s$ steps of a linear congruential generator are one map $x \mapsto Ax + C$, found by squaring. Problem 941 uses this to produce ten million generator values a row at a time: it applies the $4096$-step map to $4096$ consecutive values at once, so the sequential recurrence becomes vector arithmetic.

The period can also sit in the input, choosing the formula. Problem 984 counts certain lattice octagons on an $N \times N$ board. A count of shapes with a fixed number of integer parameters is polynomial in $N$, here of degree $8$. But one constraint changes form once a side reaches twice the other, so the count is a quasi-polynomial: one polynomial for even $N$ and another for odd $N$. Fitting each from small exact values of its own parity, and evaluating at $N = 10^{18}$, is just periodicity mod $2$ applied to the formula instead of the sequence. Fit across parities and you get a polynomial that matches neither class.

The cycle can also hide in a physical process. In problem 641 each die face cycles with period $6$, so a die ends showing 1 exactly when its turn count, $d(k) - 1$, is a multiple of 6. That is $d(k) \equiv 1 \pmod 6$. It splits into "$d(k)$ odd", which forces $k$ to be a square, and a condition mod $3$ on the prime exponents. A row of $10^{36}$ dice becomes a count of integers with a particular factorisation shape. Iteration can also stop moving. In problem 455, iterating $x \mapsto n^x \bmod 10^9$ builds the power tower $n, n^n, n^{n^n}, \dots$, and because the chain $m, \lambda(m), \lambda(\lambda(m)), \dots$ of Carmichael values shrinks to $1$ quickly, the tower goes constant within a dozen rounds. That constant is the fixed point the problem asks for, and the search never touches the $10^9$ candidates. Problem 700 turns the cycle into a different algorithm. Its sequence $na \bmod m$ sets successive record lows, and the records come from repeatedly subtracting the smaller of "current minimum" and "gap below $m$" from the larger. That is Euclid's algorithm on $(a, m)$, and it ends at $1$ when $n = a^{-1} \bmod m$. A walk over quadrillions of terms costs one step per record.

Congruences as the object of study. Sometimes the residues are not a tool but the thing being counted. Problems 271 and 272 (Modular Cubes) ask for the solutions of $x^3 \equiv 1 \pmod n$; problem 451 hunts self-inverse residues with $m^2 \equiv 1 \pmod n$; problem 801 studies pairs with $x^y \equiv y^x$. These are number theory proper — you factor the modulus, understand the structure prime power by prime power, and glue the answer back with the Chinese Remainder Theorem — and they are where the domain stops being a convenience and becomes the subject. In 272 that glue is the whole solution: the unit group modulo an odd prime power is cyclic, a cyclic group of order $k$ holds exactly $\gcd(3, k)$ cube roots of unity, and so the count of solutions is a power of $3$ read straight off the factorisation of $n$ — the search becomes one over factorisations, not over residues. Problem 421 reaches the same structure from the other side. It asks for the prime factors below $10^8$ of $n^{15} + 1$ for $10^{11}$ values of $n$, which is hopeless; swap the order of summation and ask each prime $p$ instead "for which residues $n$ does $p \mid n^{15} + 1$?" The answer is the negatives of the $15$th roots of unity mod $p$ — exactly $\gcd(15, p - 1)$ of them — and each residue class contributes its count of $n \le N$ by a single division. Factorisation turned into counting residues. Problem 457 needs a root of $n^2 - 3n - 1$ modulo $p^2$ for every prime $p \le 10^7$, and a search over $p^2$ residues is out of the question. Completing the square, which is legal because $2$ is a unit modulo an odd $p^2$, turns the quadratic into a square root of $13$. Quadratic reciprocity decides from $p \bmod 13$ whether one exists modulo $p$, and Tonelli–Shanks finds it. Hensel's lemma then lifts it to $p^2$ with one Newton step, $r \leftarrow r - (r^2 - 13)(2r)^{-1}$, which is valid because the root is simple ($2r \not\equiv 0$). To solve modulo a prime power, solve modulo the prime and then lift. Problem 407 makes the decomposition itself the answer. An idempotent, $a^2 \equiv a \pmod n$, must be $0$ or $1$ modulo each prime power of $n$, because $a$ and $a - 1$ are coprime. So the idempotents correspond to the ways of splitting $n$ into a coprime pair $d \cdot e$, and there are $2^{\omega(n)}$ of them. Finding the largest one for every $n \le 10^7$ means enumerating coprime factor pairs and solving two congruences by CRT, rather than testing residues. Problem 752 does the same for an order. It asks for the least $n$ with $(1 + \sqrt 7)^n \equiv 1$ in $(\mathbb{Z}/x\mathbb{Z})[\sqrt 7]$, for every $x$ up to $10^6$. The norm $a^2 - 7b^2$ is multiplicative, and $1 + \sqrt 7$ has norm $-6$. So it is a unit exactly when $\gcd(x, 6) = 1$, and every other $x$ contributes $0$. CRT splits the ring over the prime powers of $x$, so the order is the lcm of the orders modulo each $p^k$. Lifting from $p^{k-1}$ to $p^k$ either keeps the order or multiplies it by $p$, and a single power decides which. The real work is one order per prime: in $\mathbb{F}_p$ when $7$ is a square mod $p$, and in $\mathbb{F}_{p^2}$ otherwise, with the same Frobenius bound as problem 492 below. Problem 437 shows that the element need not even be found. For each of about three million primes it asks whether either root of $x^2 - x - 1$ modulo $p$ is a primitive root. Those roots are built from a square root of $5$, which would cost a search per prime. But when they exist, CRT splits $\mathbb{Z}_p[x]/(x^2 - x - 1)$ into two copies of $\mathbb{F}_p$, one per root. A power of the formal root $x$ is therefore both roots' powers at once, and one ring exponentiation tests the pair without naming either. Problem 875 counts solutions with the filter from the subset-sum disguise, written additively. The zeros of the eight-variable form $a_1^2 + \dots + a_4^2 - b_1^2 - \dots - b_4^2$ modulo $n$ number $\frac1n \sum_t |G(t, n)|^8$, where $G(t, n) = \sum_x e^{2\pi i t x^2 / n}$ is a quadratic Gauss sum. Its modulus is known in closed form: $|G|^2 = m$ for an odd reduced modulus $m$, with a 2-adic exception. So the count is a Dirichlet convolution of multiplicative functions, and $n^8$ tuples become a totient sieve.

A polynomial divisibility can be a congruence too. Problem 995 asks when the cyclotomic polynomial $\Phi_p$ divides $1 + \sum_{d \mid s} x^d$. Substituting a primitive $p$th root $\zeta$ makes the exponents residues mod $p$, so the condition says the divisors of $s$ hit every non-zero residue exactly once. The prime powers of $s$ then factor the cyclic group $(\mathbb{Z}/p)^\times$, and the search runs over chains of subgroups, priced by multiplicative orders. Divisibility by $\Phi_m$ or by $x^m - 1$ always reads this way: as a statement about exponents mod $m$.

The same subgroup structure can collapse a whole dynamical system. Problem 971 iterates $x \mapsto x + x^k$ modulo primes $p = 5k - 4$ and counts the periodic points. With $m = (p - 1)/5$, the map is $x(1 + \chi(x))$, where $\chi(x) = x^m$ is the quintic power residue symbol. By Fermat it is always a fifth root of unity. It splits the cyclic unit group into five cosets of $m$ elements each, and multiplying by $1 + \zeta^j$ moves a whole coset to another coset. So the $p$-point functional graph projects onto a five-node map. Each class on a cycle of that map returns multiplied by a constant, which is a bijection, so all of its elements are periodic. Each prime costs a few exponentiations instead of a walk over $p$ points. When a map acts through a character, work on the cosets of its kernel.

A congruence can also be the proof that decides the structure. Problem 960 is a solitaire game in which every turn removes exactly $n$ stones from two of $n$ piles of $n - 1$. Record the game as a graph with one edge per turn. A connected component of $k$ piles holds $k(n-1)$ stones and its turns removed a multiple of $n$, so $n \mid k(n - 1)$. Since $\gcd(n, n-1) = 1$, that forces $k = n$. The graph is a spanning tree, and the game becomes a sum over labelled trees, counted by Cayley's formula. One line of arithmetic mod $n$ replaces a simulation.

What the modulus allows

Addition and multiplication survive reduction modulo any $m$. Everything else depends on the modulus, so read it before you write the first line:

A prime modulus is a field, and every nonzero residue has an inverse. That is why setters choose $10^9 + 7$ or $1234567891$, and the primality is often load-bearing rather than cosmetic. Problem 529 finds a linear recurrence of order $2772$ with the Berlekamp–Massey algorithm, which divides by discrepancies and so needs a field; problems 996 and 1010 divide by $n!$ and by products of hook lengths, legal only because the prime exceeds every factor involved — check that inequality too, since a prime smaller than your factorials makes them vanish. A field also shrinks exponents. By Fermat, $a^{p-1} \equiv 1$, so problem 822 reduces the exponent $2^k$ of a number squared $k \approx 10^{12}$ times modulo $p - 1$, which is one modular exponentiation inside another. Sometimes the exponent cannot even be written down. Problem 520 turns its count into power sums $\sum_k c_k k^n$ for $n = \text{base}^u$, with $u$ up to $1000$ in the large case. It never forms $n$. Instead it advances $k^{\text{base}^{u-1}}$ to $k^{\text{base}^u}$ by raising it to the power $\text{base}$, and carries $n \bmod p$ separately for the $k = 1$ term, whose geometric series has no ratio to divide by. The same shrinking works one level up, in a quadratic extension. Problem 492 iterates $a \mapsto 6a^2 + 10a + 3$ a quadrillion times. Completing the square turns it into $b \mapsto b^2 - 2$, the doubling rule of a Lucas sequence $\alpha^k + \alpha^{-k}$, so the $n$th term is $V_{2^{n-1}}$. Here $\alpha$ is a root of $t^2 - 11t + 1$. If the discriminant is a square mod $p$, $\alpha$ lies in $\mathbb{F}_p$ and its order divides $p - 1$. If not, it lies in $\mathbb{F}_{p^2}$, where Frobenius sends $\alpha$ to its conjugate $\alpha^{-1}$, so $\alpha^{p+1} = 1$. Quadratic reciprocity decides between the two cases from $p \bmod 13$, and the exponent $2^{n-1}$ is reduced mod $p \mp 1$. Problem 921 is the split case, with exponents that need work of their own. A change of variable turns its recurrence into a fifth-power map, so $p_n$ and $q_n$ are the coordinates of a fixed element of $\mathbb{Z}[\sqrt 5]$ raised to the power $5^n$, and the sum runs over $n = F_i$. Its prime modulus $M$ has $5$ as a square, so exponents reduce mod $M - 1$. That square root is used only in the proof. The code stays with coordinate pairs, which are what the problem wants anyway. The exponents have a recurrence too: $5^{F_i} = 5^{F_{i-1}} \cdot 5^{F_{i-2}}$, so each costs one multiplication mod $M - 1$. That leaves one base raised to over a million exponents, all below $M$. Splitting each exponent into low and high bits reads the power from two lookup tables of about $\sqrt M$ entries, and one ring product replaces some thirty squarings. Division is legal but not free: each inverse is an exponentiation. Problem 739 needs about $10^8$ binomials, so it multiplies the whole sum through by a factorial until every term is a prefix product times a suffix product, and takes a single inverse at the end. Problem 374 changes what it carries instead. Harmonic numbers would cost an inverse per step, but the integer $j!\,H_j$ has a recurrence with no division in it. Problems 976 and 1007 apply the same scaling to series coefficients whose recurrence divides by the index $k + 1$: carrying $k!\,c_k$ cancels it, and one inverse of a factorial at the end undoes every step. When the inverses really are needed one by one, as in problem 892 with every $1/m$ up to $5 \times 10^6$, the identity $i^{-1} \equiv -\lfloor p/i \rfloor \cdot (p \bmod i)^{-1}$ reads each from an entry already in the table.
A prime decides which fast transforms exist. The number-theoretic transform needs a $2^k$th root of unity, so it works modulo $998244353 = 119 \cdot 2^{23} + 1$ and not modulo $10^9 + 7$, whose $p - 1$ has only one factor of $2$. Problem 767 needs a length-$10^5$ convolution modulo $10^9 + 7$. It computes the integer convolution and reduces afterwards: residues are split into $10$-bit limbs small enough that a floating-point FFT rounds back to exact integers. That convolution exists only because inverse factorials separate a binomial, $\binom{K}{s} = K!\,(s!)^{-1}((K-s)!)^{-1}$, into a factor per index, which needs the field again.
A composite modulus is a product of smaller problems. By the Chinese Remainder Theorem a squarefree $m = pqr$ splits into three prime fields, so you solve in each and glue. Problem 365 wants $\binom{10^{18}}{10^9}$ — over nine billion digits — modulo some twenty million products of three primes; per prime it is one application of Lucas's theorem, and the recombination factors so that only pairwise inverses are ever needed. When the moduli are not coprime, CRT comes with a condition. Problem 531 solves $x \equiv \varphi(n) \pmod n$, $x \equiv \varphi(m) \pmod m$ for some twelve million pairs of neighbouring $n, m$. With $d = \gcd(n, m)$ the system is solvable exactly when $d \mid \varphi(m) - \varphi(n)$, and then it has one solution modulo $\operatorname{lcm}(n, m)$. Dividing the linear congruence through by $d$ leaves coprime moduli and an ordinary inverse. Test the consistency first: a pair that fails it contributes $0$.
A composite modulus also takes division away, but only division by numbers that share one of its factors. Problem 506 works modulo $123454321 = 41^2 \cdot 271^2$ and divides by $10^6 - 1 = 3^3 \cdot 7 \cdot 11 \cdot 13 \cdot 37$, which is coprime to it, so the inverse exists. Check the gcd, not whether the modulus is prime. In problem 250 the answer is wanted mod $10^{16}$, and the binomial recurrence $\binom{c}{i+1} = \binom{c}{i}(c-i)/(i+1)$ divides by numbers that share factors with $10$ — no inverse exists. The two escapes are the two implementations: carry the coefficient as an exact big integer and reduce only when storing it (Python), or strip the powers of $2$ and $5$ into exponents and invert only the unit that remains (C). Reach for the second shape whenever a recurrence divides and the modulus is not prime. The commonest case is easy to miss: "the last nine digits" means mod $10^9$, and $10^9$ is even. Problem 401's closed form $x(x+1)(2x+1)/6$, with $x$ up to $10^{15}$, has no inverse of $2$ or $3$ to lean on. The cure is to divide before reducing: one of $x, x+1$ is even and one of the three factors is a multiple of 3, so divide those exactly, then reduce and multiply. When the values are too large to hold before reducing, lift the modulus instead. To divide by a fixed $k$ modulo $m$, carry the residue modulo $km$. Problem 684 needs $q = (f - r)/9$ for Fibonacci numbers $f$ with $10^{18}$-scale values, reduced mod $p$ for a linear term and mod $p - 1$ for an exponent. Running the recurrence modulo $9p$ and $9(p-1)$ keeps $r = f \bmod 9$ visible. Subtracting it leaves a multiple of $9$, and dividing yields $q$ exactly in each ring. A floor works the same way. Problem 850 wants $\lfloor S \rfloor \bmod M$ where $2S$ is an integer, so its C port carries $2S$ modulo $2M$. That keeps the parity that decides the floor, and every product still fits in 64 bits.
A residue forgets size. Once a value is reduced you can no longer compare it with another or count how often a sum wrapped. Problem 822 must repeatedly pick the smallest of numbers squared a trillion times. It decides the order with the real-valued key $\log_2\log_2 x^{2^k} = k + \log_2\log_2 x$ and uses residues only for the final sum. Problem 271 sums the cube roots of unity mod a primorial as integers, and that total is many times the modulus. Adding the CRT combinations mod $n$ would return a plausible wrong number. Problem 615 shows the escape when the order matters and the numbers are too big to compare. It wants the millionth number with at least a million prime factors. Every early member of that list carries a common factor $2^{k-s}$, and dividing it out keeps them in the same order. So the order statistic is found among ordinary 64-bit integers, and the residue appears only at the end, as $2^{k-s} \bmod m$. Cancellation is a question about size too. Problem 605 wants an irreducible fraction, modulo $10^8$, whose denominator $(2^n - 1)^2$ has some thirty million digits. Residues cannot reveal a gcd, so it is settled from structure first. Every common prime divides $\gcd(n, 2^n - 1)$, which needs only $2^n \bmod n$. Its multiplicity is read by evaluating both parts modulo a high power of that prime. Only then are the parts reduced. Reduce exactly what the statement reduces.
Mind the width. A modulus near $10^{16}$ means the product of two residues no longer fits in 64 bits, and a sum that is not reduced — problem 421's lands just under $2^{63}$ — leaves no headroom at all; estimate the magnitude before choosing the type. Problem 531 sums CRT solutions up to $\operatorname{lcm}(n, m) \approx 10^{12}$ without reduction, and a wider test window already pushes the total past $2^{63}$, so its C port accumulates in 128 bits. A modulus below $2^{30}$ works the other way. Problem 1001's DP runs modulo $1\,003\,443\,221$, so $a \cdot b + c$ fits a signed 64-bit integer before reducing. That is what lets it run as whole-vector NumPy updates, where there is no wider type to fall back on. Its recurrence uses only $+$ and $\times$, so whether that modulus is prime never matters. The fixes (__int128, a split multiply, reducing the operands first) are in the Modular Arithmetic note.

How to reason about it

The recurring cue is a question about a remainder — last digits, divisibility, a count returned mod a prime, a count of totals hitting a residue, a periodic or cyclic structure — hung on a value far too large to form directly. When you catch it:

Name the modulus first, then classify it. "Last $k$ digits" means mod $10^k$; "divisible by $d$" means residue $0$ mod $d$; a stated 1_000_000_007 means work in that ring from line one. Prime means you may divide; composite means factor it, then split by CRT or keep division out of the ring.
Reduce early and often. Never build the honest quantity and take its remainder at the end — reduce after each $+$ and $\times$ so operands stay in $[0, m)$. The classic mistake is to materialise the million-digit power or the true factorial first; the whole point is that you never have to. The exception is a value you can afford to hold exactly. Problem 612 computes $(T^2 - D - T)/2$ with $T$ near $10^{18}$ in 128-bit integers and reduces once at the end, so the halving is ordinary integer division and needs no inverse.
Substitute the modulus into the definition. When the modulus is $n + 1$ and the base is $n$, the base is $-1$. When the modulus is prime, exponents live mod $p - 1$, or mod $p + 1$ for a norm-one element of $\mathbb{F}_p[\sqrt d]$ when $d$ is not a square. Simplify the object before you compute it.
Keep roots formal. A symmetric expression in a polynomial's roots is a function of its coefficients, and a power of a root reduces in the quotient ring by that polynomial. Neither needs the root itself, whether it is complex or a modular square root. And check whether the irrational already has a residue: then it is a plain field element and needs no ring at all.
Keep size outside the ring. Orderings, comparisons, unreduced totals and the gcd of an irreducible fraction need the real magnitude or its structure, through logarithms, plain integers or a factorisation. Residues are only for the quantity the statement reduces.
Lift the modulus to keep what you will divide by. Carry a residue modulo $km$ when you must later divide exactly by $k$, or modulo a prime power when you need a valuation. To solve an equation modulo $p^k$, solve it modulo $p$ and Hensel-lift the root.
Make the residue the state. When a number is built digit by digit and only its remainder matters, prefixes with equal remainders are interchangeable. Search or count over the $m$ remainders, not over the numbers. When an equation between numbers is checked column by column, the carry is the state.
Work on cosets. A power residue symbol $x^{(p-1)/d}$ sorts the units into $d$ classes. A map that acts through the class can be studied on $d$ nodes instead of $p$.
Use a congruence as an invariant. A total that is conserved mod $n$ can force a structure, such as a component size, before anything is counted.
Collapse inputs to their residues. If only the residue of a total matters, a quarter-million elements are a census over $m$ buckets, and their generating function can live in $\mathbb{Z}[x]/(x^m - 1)$.
Look for the cycle. If a sequence is defined by adding or multiplying a constant, it is periodic mod $m$; prove the period from the factorisation of $m$, or detect it, and leap over an astronomical number of steps. If a closed form is only polynomial on each residue class of the input, fit one polynomial per class.
Ask what the modulus lets you transform. A fast convolution needs a prime with a large power of $2$ in $p - 1$. Without one, convolve exactly in small limbs and reduce afterwards.
Turn the sum around. When a sum over $n$ asks which primes divide something, summing over the primes and asking which residue classes of $n$ each one divides is often the tractable direction.
Then reach for the machinery. Powers, division, and composite moduli each have a standard device — modular exponentiation, the modular inverse, and the Chinese Remainder Theorem — all collected, with the fixed-width overflow trap, in the Modular Arithmetic note.

Learn to hear the question underneath the wording, and a problem that looks like big-integer arithmetic turns out to be a handful of operations on small numbers.

Problems107 / 242

● 0019 — Counting Sundays
● 0048 — Self Powers
● 0078 — Coin Partitions
● 0097 — Large Non-Mersenne Prime
● 0104 — Pandigital Fibonacci Ends
● 0120 — Square Remainders
● 0123 — Prime Square Remainders
● 0129 — Repunit Divisibility
● 0132 — Large Repunit Factors
● 0135 — Same Differences
● 0136 — Singleton Difference
● 0146 — Investigating a Prime Pattern
● 0152 — Sums of Square Reciprocals
● 0171 — Square Sum of the Digital Squares
● 0182 — RSA Encryption
● 0188 — Hyperexponentiation
● 0202 — Laserbeam
● 0206 — Concealed Square
● 0216 — The Primality of $2n^2 - 1$
● 0217 — Balanced Numbers
● 0218 — Perfect Right-angled Triangles
● 0225 — Tribonacci Non-divisors
● 0250 — $250250$
○ 0258 — A Lagged Fibonacci Sequence
○ 0266 — Pseudo Square Root
● 0271 — Modular Cubes, Part 1
● 0272 — Modular Cubes, Part 2
● 0274 — Divisibility Multipliers
● 0277 — A Modified Collatz Sequence
○ 0282 — The Ackermann Function
○ 0284 — Steady Squares
● 0294 — Sum of Digits - Experience #23
● 0303 — Multiples with Small Digits
● 0304 — Primonacci
○ 0312 — Cyclic Paths on Sierpiński Graphs
○ 0322 — Binomial Coefficients Divisible by 10
○ 0324 — Building a Tower
○ 0325 — Stone Game II
○ 0326 — Modulo Summations
○ 0330 — Euler's Number
● 0335 — Gathering the Beans
○ 0344 — Silver Dollar Game
○ 0356 — Largest Roots of Cubic Polynomials
○ 0364 — Comfortable Distance
● 0365 — A Huge Binomial Coefficient
● 0374 — Maximum Integer Partition Product
● 0381 — $(\text{prime}-k)$ Factorial
● 0401 — Sum of Squares of Divisors
○ 0402 — Integer-valued Polynomials
○ 0405 — A Rectangular Tiling
● 0407 — Idempotents
○ 0408 — Admissible Paths Through a Grid
○ 0409 — Nim Extreme
○ 0411 — Uphill Paths
○ 0412 — Gnomon Numbering
○ 0413 — One-child Numbers
○ 0416 — A Frog's Trip
● 0421 — Prime Factors of $n^{15}+1$
○ 0422 — Sequence of Points on a Hyperbola
● 0423 — Consecutive Die Throws
○ 0427 — $n$-sequences
● 0429 — Sum of Squares of Unitary Divisors
○ 0435 — Polynomials of Fibonacci Numbers
● 0437 — Fibonacci Primitive Roots
○ 0439 — Sum of Sum of Divisors
○ 0440 — GCD and Tiling
○ 0445 — Retractions A
○ 0446 — Retractions B
○ 0447 — Retractions C
○ 0451 — Modular Inverses
● 0455 — Powers with Trailing Digits
○ 0456 — Triangles Containing the Origin II
● 0457 — A Polynomial Modulo the Square of a Prime
● 0463 — A Weird Recurrence Relation
○ 0467 — Superinteger
○ 0474 — Last Digits of Divisors
● 0475 — Music Festival
○ 0477 — Number Sequence Game
● 0479 — Roots on the Rise
● 0487 — Sums of Power Sums
● 0492 — Exploding Sequence
○ 0495 — Writing $n$ as the Product of $k$ Distinct Positive Integers
○ 0498 — Remainder of Polynomial Division
○ 0500 — Problem 500!!!
○ 0505 — Bidirectional Recurrence
● 0506 — Clock Sequence
○ 0511 — Sequences with Nice Divisibility Properties
● 0512 — Sums of Totients of Powers
○ 0515 — Dissonant Numbers
● 0517 — A Real Recursion
● 0520 — Simbers
○ 0522 — Hilbert's Blackout
○ 0528 — Constrained Sums
● 0529 — $10$-substrings
● 0531 — Chinese Leftovers
○ 0536 — Modulo Power Identity
○ 0537 — Counting Tuples
○ 0546 — The Floor's Revenge
○ 0552 — Chinese Leftovers II
○ 0554 — Centaurs on a Chess Board
○ 0559 — Permuted Matrices
● 0565 — Divisibility of Sum of Divisors
○ 0592 — Factorial Trailing Digits 2
○ 0593 — Fleeting Medians
○ 0602 — Product of Head Counts
○ 0603 — Substring Sums of Prime Concatenations
● 0605 — Pairwise Coin-Tossing Game
● 0612 — Friend Numbers
○ 0614 — Special Partitions 2
● 0615 — The Millionth Number with at Least One Million Prime Factors
● 0619 — Square Subsets
○ 0622 — Riffle Shuffles
○ 0624 — Two Heads Are Better Than One
○ 0626 — Counting Binary Matrices
○ 0627 — Counting Products
● 0628 — Open Chess Positions
○ 0631 — Constrained Permutations
● 0635 — Subset Sums
○ 0638 — Weighted Lattice Paths
● 0641 — A Long Row of Dice
○ 0653 — Frictionless Tube
○ 0654 — Neighbourly Constraints
○ 0658 — Incomplete Words II
○ 0663 — Sums of Subarrays
○ 0666 — Polymorphic Bacteria
○ 0672 — One More One
○ 0673 — Beds and Desks
○ 0680 — Yarra Gnisrever
● 0682 — $5$-Smooth Pairs
● 0684 — Inverse Digit Sum
○ 0685 — Inverse Digit Sum II
○ 0693 — Finite Sequence Generator
○ 0696 — Mahjong
● 0700 — Eulercoin
● 0706 — $3$-Like Numbers
○ 0707 — Lights Out
○ 0709 — Even Stevens
● 0710 — One Million Members
○ 0715 — Sextuplet Norms
○ 0716 — Grid Graphs
○ 0717 — Summation of a Modular Formula
● 0719 — Number Splitting
● 0721 — High Powers of Irrational Numbers
● 0726 — Falling Bottles
○ 0728 — Circle of Coins
○ 0732 — Standing on the Shoulders of Trolls
○ 0733 — Ascending Subsequences
○ 0734 — A Bit of Prime
● 0739 — Summation of Summations
○ 0746 — A Messy Dinner
○ 0747 — Triangular Pizza
○ 0750 — Optimal Card Stacking
● 0752 — Powers of $1+\sqrt 7$
○ 0753 — Fermat Equation
● 0754 — Product of Gauss Factorials
○ 0758 — Buckets of Water
○ 0759 — A Squared Recurrence Relation
○ 0760 — Sum over Bitwise Operators
● 0767 — Window into a Matrix II
○ 0773 — Ruff Numbers
○ 0774 — Conjunctive Sequences
● 0778 — Freshman's Product
○ 0784 — Reciprocal Pairs
● 0788 — Dominating Numbers
○ 0789 — Minimal Pairing Modulo $p$
○ 0790 — Clock Grid
○ 0797 — Cyclogenic Polynomials
○ 0801 — $x^y \equiv y^x$
○ 0803 — Pseudorandom Sequence
○ 0805 — Shifted Multiples
○ 0809 — Rational Recurrence Relation
○ 0811 — Bitwise Recursion
○ 0812 — Dynamical Polynomials
○ 0813 — XOR-Powers
○ 0814 — Mezzo-forte
● 0816 — Shortest Distance Among Points
● 0820 — $N$thDigit of Reciprocals
● 0822 — Square the Smallest
○ 0823 — Factor Shuffle
○ 0824 — Chess Sliders
○ 0830 — Binomials and Powers
● 0834 — Add and Divide
○ 0835 — Supernatural Triangles
○ 0837 — Amidakuji
● 0839 — Beans in Bowls
○ 0840 — Sum of Products
● 0844 — $k$-Markov Numbers
○ 0849 — The Tournament
● 0850 — Fractions of Powers
○ 0851 — SOP and POS
○ 0854 — Pisano Periods 2
○ 0858 — LCM
○ 0865 — Triplicate Numbers
● 0866 — Tidying Up B
○ 0871 — Drifting Subsets
○ 0873 — Words with Gaps
○ 0874 — Maximal Prime Score
● 0875 — Quadruple Congruence
● 0885 — Sorted Digits
○ 0889 — Rational Blancmange
○ 0891 — Ambiguous Clock
● 0892 — Zebra Circles
○ 0902 — Permutation Powers
○ 0903 — Total Permutation Powers
○ 0909 — L-expressions I
○ 0910 — L-expressions II
● 0912 — Where are the Odds?
○ 0916 — Restricted Permutations
○ 0917 — Minimal Path Using Additive Cost
● 0921 — Golden Recurrence
○ 0924 — Larger Digit Permutation II
○ 0925 — Larger Digit Permutation III
○ 0929 — Odd-Run Compositions
● 0934 — Unlucky Primes
● 0940 — Two-Dimensional Recurrence
● 0941 — de Bruijn's Combination Lock
○ 0942 — Mersenne's Square Root
● 0943 — Self Describing Sequences
● 0944 — Sum of Elevisors
○ 0947 — Fibonacci Residues
○ 0952 — Order Modulo Factorial
○ 0956 — Super Duper Sum
● 0960 — Stone Game Solitaire
● 0967 — $B$-Trivisible Numbers
● 0968 — 5D Summation
● 0971 — Modular Polynomial Composition
● 0974 — Very Odd Numbers
● 0976 — XO Game
○ 0977 — Iterated Functions
○ 0981 — The Quaternion Group II
● 0984 — Knights and Horses
○ 0989 — Fibonacci Sum
● 0990 — Addition Equations
○ 0992 — Another Frog Jumping
● 0995 — A Particular Pair of Polynomials
● 0996 — Overtakes
○ 0999 — Alternating Recurrence
● 1000 — Problem $1000$
● 1001 — Connections I
○ 1004 — Balanced Integer
● 1007 — Alternating Difference
● 1010 — March of the Penguins