All functions take and return Expression objects holding integer leaves,
so arbitrary precision flows through the existing machinery; passing a
non-integer expression raises. (Exception: continued_fraction_rational
also accepts rational leaves; the three symbol functions return plain
machine integers.)
Prime factorization as (prime, multiplicity) pairs, ascending. Errors on
zero. Notes: WASM returns PrimeFactor objects with
prime/multiplicity getters; the sign −1 of a negative input is carried
as a leading (-1, 1) factor exactly as the core reports it.
The smallest non-negative solution of the simultaneous congruences
x≡ri(modmi). Moduli need not be pairwise coprime; inconsistent systems
raise. Notes: WASM passes a flat interleaved array
[residue_0, modulus_0, ...].
Eventually-periodic expansion of d for a non-negative integer d, returned
as (initial_terms, periodic_part). Perfect squares give a one-element
initial part and an empty period. Notes: WASM returns a
QuadraticContinuedFractionExpansion object with
initial_terms/periodic_terms getters.
quadratic_continued_fraction_expansion (WASM result class)#
The two supported Diophantine subclasses are linear
equations via the extended Euclidean algorithm and Pell's equation via the
continued fraction of D. General Diophantine solving is undecidable
(Matiyasevich–Robinson–Davis–Putnam) and is out of scope; the solvers return
exact integers and never guess.
General integer solution of a1x1+…+anxn=c, returned as the parametric
coordinates — one expression per unknown, affine in fresh integer parameter
symbols (diophantine_parameter_k) shared across the coordinates so that
choosing any integers for the parameters yields a solution tuple. The list is
empty only when the equation provably has no integer solution
(gcd(ai)∤c). When every coefficient and the constant are zero, each
coordinate is its own fresh integer parameter. All coefficients and the constant
must be integer expression leaves; any other input, including an empty coefficient
list, raises a declined-computation error instead of returning an empty list.
General integer solution of the rectangular system Ax=b, returned as one
parametric coordinate expression per column of A. The coordinates share fresh
integer parameter symbols and describe the complete affine integer lattice of
solutions. The list is empty only when the system provably has no integer
solution. A row count of A that differs from the number of constants raises a
length-mismatch error, and an entry that is not an integer expression leaf raises
a declined-computation error.
Fundamental solution [x, y] of x2−Dy2=1 for a positive non-square
integer D, the smallest positive solution from which all others are generated
by the recurrence xk+1=x1xk+Dy1yk, yk+1=x1yk+y1xk. The list is
empty when D is a perfect square or non-positive (no nontrivial fundamental
solution). A radicand that is not an exact integer raises an integer-required
error.
Fundamental solution [x, y] of the negative-Pell equation x2−Dy2=−1
when it is solvable (exactly when the continued fraction of D has odd period),
and an empty list for an integer D for which it is not. A radicand that is not an
exact integer raises an integer-required error.
The first count positive solutions of x2−Dy2=1, materialised from the
fundamental solution by the Pell recurrence and returned as a flat list
[x1,y1,x2,y2,…]. Empty when the integer D has no fundamental
solution; a radicand that is not an exact integer raises an integer-required error.
solve_integers is the deliberate integer-domain solver. It takes a conjunction of
equations and linear congruences in an ordered list of integer unknowns, and either
states the complete integer solution set or declines with a typed reason. It never
returns a few sampled solutions as if they were all of them, and it never reports
"no solution" for a problem it could not decide. General Diophantine equations are
undecidable, so the accepted classes are deliberately narrow:
Request
Result
One unknown, rational-coefficient polynomial or rational equations
finite, empty, or lattice_family (every integer except undefined_points)
One unknown, linear congruences, with or without equations
congruence_family (one residue class), finite, or empty
Several unknowns, affine equations and congruences
lattice_family, finite, or empty, by Smith normal form
Two unknowns, one equation a*x^2 + b*y^2 + c = 0 reducing to x^2 - D*y^2 = N
Each equation is an equation or an expression meaning expression = 0. Congruence
i states that congruences[i] vanishes modulo the positive integer moduli[i];
congruences are passed through this typed boundary, never parsed from mod syntax,
and must be affine with integer coefficients. An empty or repeated unknown list, a
moduli list of a different length, a modulus that is not a positive integer, and a
zero limit are errors, not declines.
Every report that is not declined reads the same way. The integer solutions are
exactly the tuples obtained by substituting integers for parameters into one of the
solutions, other than the undefined_points. The three kinds of answer are kept
apart:
finite and empty have no parameters: solutions is the whole enumerated set,
and an empty list is a proof of no solution.
lattice_family and congruence_family are unbounded integer parameter families:
6*x + 9*y = 21 gives one tuple affine in one parameter, with its
lattice_particular point and Hermite-reduced lattice_basis; 6x≡9(mod15)
gives x = 4 + 5*k with residue 4 and modulus 5.
pell_orbits is a union of orbits under multiplication by the norm-one unit, not a
list of samples. x^2 - 5*y^2 = 4 reports its pell_equation, the unit (9, 4),
one seed per orbit, and two closed-form tuples per seed, one for each sign, exact
in an integer exponent k. Every orbit is covered because each solution has
exactly one representative in the unit's fundamental interval, and the scan of that
interval is exhaustive.
Source definedness is kept: 1/(x - 1) = 0 is empty, and undefined_points still
lists 1. A request whose proof would exceed a limit declines rather than returning
part of the answer: a generalized Pell scan needing more than
maximum_seed_candidates ordinates declines with seed_candidate_limit, and an
integer or unit longer than maximum_integer_bits bits declines with
integer_size_limit or fundamental_unit_limit. x^3 + y^3 + z^3 = 3 declines with
unsupported_class. Python returns a dictionary with one key per report field below;
WASM, Kotlin, and Swift return an IntegerSolveReport object.
Getter on IntegerSolveReport: the kinds of exact evidence the result rests on, such
as integer_root_theorem, chinese_remainder, smith_normal_form, or
pell_fundamental_interval.