Number Theory Cheatsheet

Use this page when divisibility, residues, or algebraic constraints appear and you want the smallest reliable helper.

Do Not Use When

• the core task is counting structure rather than arithmetic structure
• the problem is really implementation-heavy modular DP rather than number theory
• you have not yet separated “integer fact” from “mod prime computation”

Core Tools

• gcd(a, b)
• lcm(a, b) = a / gcd(a, b) * b
• prime factorization
• SPF sieve
• fast power
• modular inverse
• Bezout / extended Euclid

Choose By Signal

• repeated powers modulo MOD -> Modular Arithmetic hot sheet
• many nCk mod prime queries -> Modular Arithmetic hot sheet
• ax + by = c or inverse under composite modulus -> Modular Arithmetic hot sheet
• recover one square root from x^2 ≡ a (mod p) under one prime modulus -> Modular Square Root hot sheet
• find one generator of the nonzero residues modulo prime p -> Primitive Root hot sheet
• factor one 64-bit integer into sorted prime factors -> Pollard-Rho hot sheet
• recover x from a^x ≡ b (mod m) with square-root meet-in-the-middle -> Discrete Log hot sheet
• gcd/divisor counting over all multiples -> Mobius hot sheet
• summatory arithmetic functions opened through one divisor-side floor-sum -> Dirichlet prefix sums hot sheet
• implicit prefix sums of phi / mu on the quotient set Q_n -> Min_25 / Du Jiao hot sheet
• plain divisibility / factors / totients -> number-theory-basics.cpp

Prime-Exponent View

gcd: take the smaller exponent
lcm: take the larger exponent

Core Invariants

• modular division is only legal when an inverse exists
• prime-factor views turn gcd and lcm into exponentwise min/max
• repeated-power problems usually reduce to fast exponentiation before anything fancier

Typical Signals

• divisibility
• repeated factorizations
• counting modulo a prime
• legal or illegal modular division
• combinatorics under one fixed prime modulus

Quick Anchors In This Repo

• modular power / tower reasoning -> Modular Arithmetic hot sheet + Exponentiation II
• gcd / divisibility -> GCD / LCM + CRYPTKEY
• exponent recovery modulo one contest-sized modulus -> Discrete Log hot sheet + Discrete Logarithm Mod
• modular square-root extraction modulo one prime -> Modular Square Root hot sheet + Sqrt Mod
• primitive-root finding modulo one prime -> Primitive Root hot sheet + Primitive Root
• 64-bit integer factorization -> Pollard-Rho hot sheet + Factorize
• divisor-side inclusion-exclusion -> Counting Coprime Pairs
• quotient-grouped summatory sigma -> Sum of Divisors
• quotient-set prefix phi -> Sum of Totient Function
• broader workflow -> Modular Arithmetic topic

Main Trap

The most common wrong turn is treating “mod arithmetic” as if every denominator were invertible, or treating lcm(a, b) as safe without thinking about overflow in a / gcd(a, b) * b.

Reopen Paths

• topic pages -> Modular Arithmetic, Number Theory Basics, GCD / LCM, BSGS / Discrete Log, Modular Square Root / Discrete Root, Primitive Root, Pollard-Rho, Mobius And Multiplicative Counting, Dirichlet Convolution / Prefix Sums Of Number-Theoretic Functions, Min_25 / Du Jiao
• exact quick sheet -> Modular Arithmetic hot sheet
• exact exponent-recovery sheet -> Discrete Log hot sheet
• exact root-extraction sheet -> Modular Square Root hot sheet
• exact generator-finding sheet -> Primitive Root hot sheet
• exact 64-bit factorization sheet -> Pollard-Rho hot sheet
• exact gcd/divisor quick sheet -> Mobius hot sheet
• exact prefix-sum quick sheet -> Dirichlet prefix sums hot sheet
• exact implicit prefix-sum quick sheet -> Min_25 / Du Jiao hot sheet
• template layer -> Template library