modular-arithmetic
Scannednpx machina-cli add skill parcadei/Continuous-Claude-v3/modular-arithmetic --openclawModular Arithmetic
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)^{...}
- Tonelli-Shanks for square roots
-
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
Z3_Crt
uv run python -m runtime.harness scripts/z3_solve.py prove "solution_exists_iff_pairwise_coprime"
Sympy_Euler_Phi
uv run python -m runtime.harness scripts/sympy_compute.py simplify "phi(p**k) == p**(k-1)*(p-1)"
Z3_Quadratic_Residue
uv run python -m runtime.harness scripts/z3_solve.py prove "legendre_symbol_multiplicative"
Key Techniques
From indexed textbooks:
- [Graph Theory (Graduate Texts in Mathematics (173))] By N we denote the set of natural numbers, including zero. The set Z/nZ of integers modulo n is denoted by Zn; its elements are written as i := i + nZ. When we regard Z2 = {0, 1} as a eld, we also denote it as F2 = {0, 1}.
Cognitive Tools Reference
See .claude/skills/math-mode/SKILL.md for full tool documentation.
Source
git clone https://github.com/parcadei/Continuous-Claude-v3/blob/main/.claude/skills/math/graph-number-theory/modular-arithmetic/SKILL.mdView on GitHub Overview
Learn problem-solving techniques for modular arithmetic in graph number theory. It covers key methods—Extended Euclidean Algorithm for inverses, CRT for combining congruences, Euler's theorem for reducing exponents, quadratic residues with Tonelli-Shanks, and order/primitive roots for cycle structure.
How This Skill Works
Identify the congruence or system in your graph problem, verify coprimality constraints, and apply the appropriate algorithm. Use computational tools to compute inverses, solve CRT systems, or reduce exponents, then apply the results back to the graph constraints. The techniques span inverses, CRT, Euler reductions, quadratic residues, and order/primitive roots to analyze residue classes and cycles.
When to Use It
- Solving linear congruences by finding modular inverses when gcd(a, n) = 1.
- Merging multiple congruences with coprime moduli using the Chinese Remainder Theorem.
- Reducing large exponents modulo n using Euler's theorem and phi(n) formulas.
- Testing quadratic residuosity and computing square roots modulo primes (Tonelli-Shanks).
- Analyzing multiplicative structure by computing ord_n(a) and identifying primitive roots in Zn.
Quick Start
- Step 1: Identify the modular equation or system in your graph problem.
- Step 2: Choose and run the relevant tool command to compute inverses, CRT, Euler reductions, or residues (examples below).
- Step 3: Apply the computed result to your graph constraints and verify consistency.
Best Practices
- Always verify gcd(a, n) = 1 before attempting to compute a^{-1} mod n.
- For CRT, ensure moduli are pairwise coprime and compute a single combined solution modulo prod(m_i).
- Use Euler's theorem to reduce exponents only when gcd(a, n) = 1; know phi(p^k) = p^{k-1}(p-1).
- When dealing with square roots, apply Legendre symbols and Tonelli-Shanks as appropriate.
- Compute ord_n(a) to understand the cycle length and identify potential primitive roots within Zn.
Example Use Cases
- Example 1: In a graph labeling problem, compute a^{-1} mod n to linearize constraints and solve for a valid labeling.
- Example 2: Merge several modular constraints from different graph components using CRT to obtain a global solution.
- Example 3: Reduce a^k mod n when counting walks or paths with modular periodicity in a graph.
- Example 4: Use Tonelli-Shanks to find sqrt(a) mod p for assigning weights in a modular graph labeling problem.
- Example 5: Determine the order of an element to assess cycle lengths or confirm whether an element is a primitive root in a modular graph model.
