Modular Arithmetic

Modular Arithmetic

When to Use

Use this skill when working on modular-arithmetic problems in graph number theory.

Decision Tree

1. Extended Euclidean Algorithm

   • Find gcd(a,b) and x,y with ax + by = gcd(a,b)
   • Modular inverse: a^{-1} mod n when gcd(a,n) = 1
   • sympy_compute.py solve "a*x == 1 mod n"

2. Chinese Remainder Theorem

   • System x = a_i (mod m_i) with coprime m_i
   • Unique solution mod prod(m_i)
   • z3_solve.py prove "crt_solution_exists"

3. Euler's Theorem

   • a^{phi(n)} = 1 (mod n) when gcd(a,n) = 1
   • phi(p^k) = p^{k-1}(p-1)
   • sympy_compute.py simplify "euler_phi"

4. Quadratic Residues

   • Legendre symbol: (a/p) = a^{(p-1)/2} mod p
   • Quadratic reciprocity: (p/q)(q/p) = (-1)^{...}
   • Tonelli-Shanks for square roots

5. Order and Primitive Roots

   • ord_n(a) = smallest k with a^k = 1 (mod n)
   • Primitive root: ord_n(a) = phi(n)

Tool Commands

Sympy_Mod_Inverse

uv run python -m runtime.harness scripts/sympy_compute.py solve "a*x == 1 mod n" --var x