• i. GCD and Extended Euclid: $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$ with $\gcd (a,0)=|a|$; it runs in $O(\log \min (a,b))$ steps (worst case:
• ii. Linear Congruences and CRT: Everything here is extended Euclid (GCD and Extended Euclid) plus careful division.
• iii. Primes and Sieves: Sieving flips “for each $n$, look at its divisors” into “for each $d$, touch its multiples”:
• iv. Primality Testing and Factorization: using u64 = unsigned long long; using u128 = __uint128_t;
• v. Arithmetic Functions and Möbius: $\phi (n)$ counts the integers in $[1,n]$ coprime to $n$.
• vi. Harmonic Lemma and Floor Sums: $\lfloor n/i\rfloor$ takes at most $O(\sqrt{n})$ distinct values as $i$ ranges over $1,2,\dots ,n$.
• vii. Sublinear Sieves and Prime Counting: Prefix sums of Euler’s phi and the Mobius function up to n ~ 1e10 in O(n^{2/3}) using Dirichlet convolution identities.
• viii. Factorials and Binomials mod p: Computing $n!\mathrm{mod}m$ and $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}m$ — the case analysis depends entirely on how $m$ relates to $n$.
• ix. Primitive Roots and Discrete Log: Group structure of (Z/nZ)*:
• x. Quadratic Residues and Modular Roots: $a$ is a quadratic residue modulo $p$ if $x^2\equiv a$ has a solution.
• xi. Continued Fractions and Pell Equations: Continued fractions, convergents, closest fractions with bounded denominator and binary search over fractions.
• xii. Number Theory Miscellany: AP intersections, coprime bases, Pythagorean triples, counting roots of 1 and k-th powers, Fibonacci and Zeckendorf, power towers, balanced ternary, elliptic curves, Gaussian integers.