Skip to content
Symi Docs
Python
On this page

Integer number theory

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.)

is_prime#

Default context

is_prime(n: ExpressionLike) -> Optional[bool]
Calling forms

Explicit context: Context.is_prime

is_prime(n: ExpressionLike) -> Optional[bool]

Expression method: Expression.is_prime

is_prime() -> Optional[bool]

Deterministic primality verdict; None when the input is outside the classifier's domain (e.g. not a natural number ≥0\geq 0 representation it handles).

factor_integer#

Default context

factor_integer(n: ExpressionLike) -> list[tuple[Expression, int]]
Calling forms

Explicit context: Context.factor_integer

factor_integer(n: ExpressionLike) -> list[tuple[Expression, int]]

Prime factorization as (prime, multiplicity) pairs, ascending. Errors on zero. Notes: WASM returns PrimeFactor objects with prime/multiplicity getters; the sign −1-1 of a negative input is carried as a leading (-1, 1) factor exactly as the core reports it.

prime_factor (WASM result class)#

prime#

Not exposed by the Python bindings. Available as api::Session::prime in Rust.

multiplicity#

Not exposed by the Python bindings. Available as UniffiRootMultiplicity.multiplicity in Kotlin, UniffiRootMultiplicity.multiplicity in Swift, api::results::PrimeFactor::multiplicity in Rust.

integer_gcd#

Default context

integer_gcd(a: ExpressionLike, b: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.integer_gcd

integer_gcd(a: ExpressionLike, b: ExpressionLike) -> Expression

Greatest common divisor (non-negative).

integer_lcm#

Default context

integer_lcm(a: ExpressionLike, b: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.integer_lcm

integer_lcm(a: ExpressionLike, b: ExpressionLike) -> Expression

Least common multiple.

extended_euclidean#

Default context

extended_euclidean(
    a: ExpressionLike,
    b: ExpressionLike,
) -> tuple[Expression, Expression, Expression]
Calling forms

Explicit context: Context.extended_euclidean

extended_euclidean(
    a: ExpressionLike,
    b: ExpressionLike,
) -> tuple[Expression, Expression, Expression]

(gcd, x, y) with ax+by=gcd⁡a x + b y = \operatorname{gcd}. Notes: WASM returns a 3-element array [gcd, x, y].

modular_power#

Default context

modular_power(
    base: ExpressionLike,
    exponent: ExpressionLike,
    modulus: ExpressionLike,
) -> Expression
Calling forms

Explicit context: Context.modular_power

modular_power(
    base: ExpressionLike,
    exponent: ExpressionLike,
    modulus: ExpressionLike,
) -> Expression

base^exponent mod modulus by square-and-multiply; requires positive modulus and non-negative exponent.

modular_inverse#

Default context

modular_inverse(
    value: ExpressionLike,
    modulus: ExpressionLike,
) -> Expression
Calling forms

Explicit context: Context.modular_inverse

modular_inverse(
    value: ExpressionLike,
    modulus: ExpressionLike,
) -> Expression

Multiplicative inverse of value modulo modulus; errors when gcd⁡(value⁡,modulus⁡)≠1\operatorname{gcd}(\operatorname{value}, \operatorname{modulus}) \ne 1.

chinese_remainder#

Default context

chinese_remainder(residues_and_moduli: Iterable[tuple[ExpressionLike, ExpressionLike]]) -> Expression
Calling forms

Explicit context: Context.chinese_remainder

chinese_remainder(residues_and_moduli: Iterable[tuple[ExpressionLike, ExpressionLike]]) -> Expression

The smallest non-negative solution of the simultaneous congruences x≡ri(modmi)x \equiv r_i \pmod{m_i}. Moduli need not be pairwise coprime; inconsistent systems raise. Notes: WASM passes a flat interleaved array [residue_0, modulus_0, ...].

euler_totient#

Default context

euler_totient(n: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.euler_totient

euler_totient(n: ExpressionLike) -> Expression

Euler's φ(n)\varphi(n); requires a positive integer.

mobius#

Default context

mobius(n: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.mobius

mobius(n: ExpressionLike) -> Expression

Möbius μ(n)∈{−1,0,1}\mu(n) \in \{-1, 0, 1\}; requires a positive integer.

divisor_count#

Default context

divisor_count(n: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.divisor_count

divisor_count(n: ExpressionLike) -> Expression

Number of positive divisors τ(n)\tau(n).

divisor_sigma#

Default context

divisor_sigma(n: ExpressionLike, power: int) -> Expression
Calling forms

Explicit context: Context.divisor_sigma

divisor_sigma(n: ExpressionLike, power: int) -> Expression

Sum of the power-th powers of the positive divisors σpower(n)\sigma_{\mathit{power}}(n); power = 0 gives divisor_count, power = 1 the divisor sum.

jacobi_symbol#

Default context

jacobi_symbol(
    numerator: ExpressionLike,
    denominator: ExpressionLike,
) -> int
Calling forms

Explicit context: Context.jacobi_symbol

jacobi_symbol(
    numerator: ExpressionLike,
    denominator: ExpressionLike,
) -> int

The Jacobi symbol (n/d)∈{−1,0,1}(n/d) \in \{-1, 0, 1\}; the denominator must be a positive odd integer.

legendre_symbol#

Default context

legendre_symbol(numerator: ExpressionLike, prime: ExpressionLike) -> int
Calling forms

Explicit context: Context.legendre_symbol

legendre_symbol(numerator: ExpressionLike, prime: ExpressionLike) -> int

The Legendre symbol; the second argument must be an odd prime.

kronecker_symbol#

Default context

kronecker_symbol(
    numerator: ExpressionLike,
    denominator: ExpressionLike,
) -> int
Calling forms

Explicit context: Context.kronecker_symbol

kronecker_symbol(
    numerator: ExpressionLike,
    denominator: ExpressionLike,
) -> int

The Kronecker extension of the Jacobi symbol to all integer denominators.

integer_square_root#

Default context

integer_square_root(n: ExpressionLike) -> Expression
Calling forms

Explicit context: Context.integer_square_root

integer_square_root(n: ExpressionLike) -> Expression

⌊n⌋\lfloor\sqrt{n}\rfloor for non-negative n.

integer_nth_root#

Default context

integer_nth_root(n: ExpressionLike, root_index: int) -> Expression
Calling forms

Explicit context: Context.integer_nth_root

integer_nth_root(n: ExpressionLike, root_index: int) -> Expression

⌊n1/root_index⌋\lfloor n^{1/\mathit{root\_index}}\rfloor; odd indices accept negative n. Errors when no real root exists (even index, negative n).

continued_fraction_rational#

Default context

continued_fraction_rational(value: ExpressionLike) -> list[Expression]
Calling forms

Explicit context: Context.continued_fraction_rational

continued_fraction_rational(value: ExpressionLike) -> list[Expression]

Terminating continued-fraction expansion [a0; a1, a2, ...] of an integer or rational expression leaf.

continued_fraction_quadratic_irrational#

Default context

continued_fraction_quadratic_irrational(value: ExpressionLike) -> tuple[list[Expression], list[Expression]]
Calling forms

Explicit context: Context.continued_fraction_quadratic_irrational

continued_fraction_quadratic_irrational(value: ExpressionLike) -> tuple[list[Expression], list[Expression]]

Eventually-periodic expansion of d\sqrt{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)#

initial_terms#

Not exposed by the Python bindings. Available as UniffiQuadraticContinuedFractionExpansion.initialTerms in Kotlin, UniffiQuadraticContinuedFractionExpansion.initialTerms in Swift, api::results::QuadraticContinuedFractionExpansion::initial_terms in Rust.

periodic_terms#

Not exposed by the Python bindings. Available as UniffiQuadraticContinuedFractionExpansion.periodicTerms in Kotlin, UniffiQuadraticContinuedFractionExpansion.periodicTerms in Swift, api::results::QuadraticContinuedFractionExpansion::periodic_terms in Rust.

Diophantine equations#

The two supported Diophantine subclasses are linear equations via the extended Euclidean algorithm and Pell's equation via the continued fraction of D\sqrt{D}. General Diophantine solving is undecidable (Matiyasevich–Robinson–Davis–Putnam) and is out of scope; the solvers return exact integers and never guess.

solve_linear_diophantine#

Default context

solve_linear_diophantine(
    coefficients: Iterable[ExpressionLike],
    constant: ExpressionLike,
) -> list[Expression]
Calling forms

Explicit context: Context.solve_linear_diophantine

solve_linear_diophantine(
    coefficients: Iterable[ExpressionLike],
    constant: ExpressionLike,
) -> list[Expression]

General integer solution of a1x1+…+anxn=ca_1 x_1 + \ldots + a_n x_n = 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\gcd(a_i) \nmid 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.

solve_linear_diophantine_system#

Default context

solve_linear_diophantine_system(
    coefficient_matrix: Matrix,
    constants: Iterable[ExpressionLike],
) -> list[Expression]
Calling forms

Explicit context: Context.solve_linear_diophantine_system

solve_linear_diophantine_system(
    coefficient_matrix: Matrix,
    constants: Iterable[ExpressionLike],
) -> list[Expression]

General integer solution of the rectangular system Ax=bA x = 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.

solve_pell#

Default context

solve_pell(radicand: ExpressionLike) -> list[Expression]
Calling forms

Explicit context: Context.solve_pell

solve_pell(radicand: ExpressionLike) -> list[Expression]

Fundamental solution [x, y] of x2−Dy2=1x^2 - D y^2 = 1 for a positive non-square integer D, the smallest positive solution from which all others are generated by the recurrence xk+1=x1xk+Dy1ykx_{k+1} = x_1 x_k + D y_1 y_k, yk+1=x1yk+y1xky_{k+1} = x_1 y_k + y_1 x_k. 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.

solve_negative_pell#

Default context

solve_negative_pell(radicand: ExpressionLike) -> list[Expression]
Calling forms

Explicit context: Context.solve_negative_pell

solve_negative_pell(radicand: ExpressionLike) -> list[Expression]

Fundamental solution [x, y] of the negative-Pell equation x2−Dy2=−1x^2 - D y^2 = -1 when it is solvable (exactly when the continued fraction of D\sqrt{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.

pell_solutions#

Default context

pell_solutions(radicand: ExpressionLike, count: int) -> list[Expression]
Calling forms

Explicit context: Context.pell_solutions

pell_solutions(radicand: ExpressionLike, count: int) -> list[Expression]

The first count positive solutions of x2−Dy2=1x^2 - D y^2 = 1, materialised from the fundamental solution by the Pell recurrence and returned as a flat list [x1,y1,x2,y2,…][x_1, y_1, x_2, y_2, \ldots]. Empty when the integer D has no fundamental solution; a radicand that is not an exact integer raises an integer-required error.

Integer-domain solving#

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 pell_orbits, finite, or empty
Anything else, including symbolic parameters declined with unsupported_class

solve_integers#

Default context

solve_integers(
    equations: Iterable[ExpressionLike],
    unknowns: Iterable[VariableLike],
    congruences: Optional[Iterable[ExpressionLike]] = ...,
    moduli: Optional[Iterable[ExpressionLike]] = ...,
    maximum_seed_candidates: int = ...,
    maximum_integer_bits: int = ...,
) -> Any
Calling forms

Explicit context: Context.solve_integers

solve_integers(
    equations: Iterable[ExpressionLike],
    unknowns: Iterable[VariableLike],
    congruences: Optional[Iterable[ExpressionLike]] = ...,
    moduli: Optional[Iterable[ExpressionLike]] = ...,
    maximum_seed_candidates: int = ...,
    maximum_integer_bits: int = ...,
) -> Any

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)6x \equiv 9 \pmod{15} 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.

IntegerSolveReport#

Not exposed by the Python bindings. Available as api::IntegerSolveReport in Rust.

What solve_integers returns. complete is false only for a declined report.

integer_report_verdict#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.verdict in Kotlin, UniffiIntegerSolveReport.verdict in Swift, api::results::IntegerSolveReport::verdict in Rust.

Getter on IntegerSolveReport: finite, empty, lattice_family, congruence_family, pell_orbits, or declined.

integer_report_complete#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.complete in Kotlin, UniffiIntegerSolveReport.complete in Swift, api::results::IntegerSolveReport::complete in Rust.

Getter on IntegerSolveReport: whether the report states the whole integer solution set.

integer_report_unknowns#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.unknowns in Kotlin, UniffiIntegerSolveReport.unknowns in Swift, api::results::IntegerSolveReport::unknowns in Rust.

Getter on IntegerSolveReport: the requested unknowns, in the order every tuple uses.

integer_report_solutions#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.solutions in Kotlin, UniffiIntegerSolveReport.solutions in Swift, api::results::IntegerSolveReport::solutions in Rust.

Getter on IntegerSolveReport: the solution tuples, exact in the integer parameters.

integer_report_parameters#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.parameters in Kotlin, UniffiIntegerSolveReport.parameters in Swift, api::results::IntegerSolveReport::parameters in Rust.

Getter on IntegerSolveReport: the parameters of the solution tuples, each ranging over every integer.

integer_report_undefined_points#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.undefinedPoints in Kotlin, UniffiIntegerSolveReport.undefinedPoints in Swift, api::results::IntegerSolveReport::undefined_points in Rust.

Getter on IntegerSolveReport: the integer points at which some source equation is undefined. No solution is one of them.

integer_report_lattice_particular#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.latticeParticular in Kotlin, UniffiIntegerSolveReport.latticeParticular in Swift, api::results::IntegerSolveReport::lattice_particular in Rust.

Getter on IntegerSolveReport: one point of the solution lattice of a lattice_family report.

integer_report_lattice_basis#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.latticeBasis in Kotlin, UniffiIntegerSolveReport.latticeBasis in Swift, api::results::IntegerSolveReport::lattice_basis in Rust.

Getter on IntegerSolveReport: a Hermite-reduced basis of the direction lattice of a lattice_family report.

integer_report_residue#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.residue in Kotlin, UniffiIntegerSolveReport.residue in Swift, api::results::IntegerSolveReport::residue in Rust.

Getter on IntegerSolveReport: the least nonnegative member of the class of a congruence_family report.

integer_report_modulus#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.modulus in Kotlin, UniffiIntegerSolveReport.modulus in Swift, api::results::IntegerSolveReport::modulus in Rust.

Getter on IntegerSolveReport: the positive modulus of the class of a congruence_family report.

integer_report_pell_equation#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.pellEquation in Kotlin, UniffiIntegerSolveReport.pellEquation in Swift, api::results::IntegerSolveReport::pell_equation in Rust.

Getter on IntegerSolveReport: the normalized equation x^2 - D*y^2 = N of a pell_orbits report, written in the unknowns.

integer_report_pell_unit#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.pellUnit in Kotlin, UniffiIntegerSolveReport.pellUnit in Swift, api::results::IntegerSolveReport::pell_unit in Rust.

Getter on IntegerSolveReport: the fundamental solution (u, v) of u^2 - D*v^2 = 1 that generates every orbit.

integer_report_pell_seeds#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.pellSeeds in Kotlin, UniffiIntegerSolveReport.pellSeeds in Swift, api::results::IntegerSolveReport::pell_seeds in Rust.

Getter on IntegerSolveReport: one seed per orbit, in the order of the requested unknowns.

integer_report_proof_methods#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.proofMethods in Kotlin, UniffiIntegerSolveReport.proofMethods in Swift, api::results::IntegerSolveReport::proof_methods in Rust.

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.

integer_report_decline_reason#

Not exposed by the Python bindings. Available as UniffiIntegerSolveReport.declineReason in Kotlin, UniffiIntegerSolveReport.declineReason in Swift, api::results::IntegerSolveReport::decline_reason in Rust.

Getter on IntegerSolveReport: why the solve made no claim, present exactly when the verdict is declined.

IntegerSolutionTuple#

Not exposed by the Python bindings. Available as api::IntegerSolutionTuple in Rust.

One exact tuple of a report, with one coordinate per requested unknown.

integer_tuple_coordinates#

Not exposed by the Python bindings. Available as UniffiIntegerSolutionTuple.coordinates in Kotlin, UniffiIntegerSolutionTuple.coordinates in Swift, api::results::IntegerSolutionTuple::coordinates in Rust.

Getter on IntegerSolutionTuple: the coordinates, in the order of the requested unknowns.

Example#

Arbitrary-precision integer arithmetic with exact structure.

Python
import symi

print(symi.is_prime(2**61 - 1))
print(symi.factor_integer(360))
print(symi.euler_totient(360))
print(symi.extended_euclidean(240, 46))
print(symi.modular_power(7, 1000, 13))

Symi documentation · Python