Prime Numbers

When to Use

Use this skill when working on prime-numbers problems in graph number theory.

Decision Tree

1. Primality testing hierarchy

- Trial division: O(sqrt(n)), exact - Miller-Rabin: O(k log^3 n), probabilistic - AKS: O(log^6 n), deterministic polynomial

1. Factorization

- Trial division for small factors - Pollard's rho: probabilistic, medium numbers - Quadratic sieve: large numbers - sympy_compute.py factor "n"

1. Prime distribution

- Prime Number Theorem: pi(x) ~ x/ln(x) - Prime gaps: p{n+1} - pn - sympy_compute.py limit "pi(x) * ln(x) / x"

1. Fermat's Little Theorem

- a^{p-1} = 1 (mod p) for a not divisible by p - Use for modular exponentiation - z3solve.py prove "fermatlittle"

1. Wilson's Theorem

- (p-1)! = -1 (mod p) iff p is prime

Tool Commands

Sympy_Factor

uv run python -m runtime.harness scripts/sympy_compute.py factor "n"

Z3_Primality

uv run python -m runtime.harness scripts/z3_solve.py prove "no_divisor_between_1_and_sqrt_n"

SympyPrimeCount

uv run python -m runtime.harness scripts/sympy_compute.py simplify "pi(x) ~ x/ln(x)"

Z3FermatLittle

uv run python -m runtime.harness scripts/z3_solve.py prove "a**(p-1) == 1 mod p"

Key Techniques

From indexed textbooks:

Cognitive Tools Reference

See .claude/skills/math-mode/SKILL.md for full tool documentation.