Name: Modular Arithmetic
Author: parcadei

When to Use

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

Decision Tree

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"
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"
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"
Quadratic Residues
- Legendre symbol: (a/p) = a^{(p-1)/2} mod p
- Quadratic reciprocity: (p/q)(q/p) = (-1)^{...}