Module diophantine 

Diophantine equations. Diophantine equations: linear ax + by = c, Pell x² − Dy² = 1, sums of two squares, and Pythagorean triples.

All arithmetic is exact (BigInt). Functions accept any integer type via impl Into<BigInt> like the rest of the number-theory API.

Examples

use symplex::diophantine::{linear_diophantine, pell, sum_of_two_squares};
use num_bigint::BigInt;

// 12x + 18y = 30 has solutions x = -5 + 3k, y = 5 - 2k  (up to the sign
// convention of the particular solution)
let sol = linear_diophantine(12, 18, 30).unwrap();
assert_eq!(BigInt::from(12) * &sol.x + BigInt::from(18) * &sol.y, BigInt::from(30));
assert_eq!(BigInt::from(12) * &sol.x_step + BigInt::from(18) * &sol.y_step, BigInt::from(0));

// Fundamental solution of x² − 61y² = 1
let (x, y) = pell(61).unwrap();
assert_eq!(x, BigInt::from(1_766_319_049u64));
assert_eq!(y, BigInt::from(226_153_980u64));

// 25 = 3² + 4²
assert_eq!(sum_of_two_squares(25), Some((BigInt::from(3), BigInt::from(4))));

Structs

LinearDiophantine

The solution family of a linear Diophantine equation a·x + b·y = c, as returned by linear_diophantine.

Functions

frobenius_number

Frobenius number of a set of positive integers with gcd = 1: the largest integer not representable as a non-negative integer combination of them.

linear_diophantine

Solve a·x + b·y = c over the integers.

linear_diophantine_n

Solve Σ coeffsᵢ · xᵢ = c over the integers for any number of variables.

pell

Fundamental (smallest positive) solution of the Pell equation x² − D·y² = 1, via the continued fraction of √D.

pell_negative

Fundamental solution of the negative Pell equation x² − D·y² = −1, if one exists (it does iff the continued-fraction period of √D has odd length).

pell_solutions

The first count positive solutions of x² − D·y² = 1, generated from the fundamental solution by Brahmagupta composition (x₁, y₁)·(x, y) = (x₁x + D y₁y, x₁y + y₁x).

pythagorean_triples

All primitive Pythagorean triples (a, b, c) with a < b < c ≤ limit, generated by Euclid’s formula a = m² − n², b = 2mn, c = m² + n² over coprime m > n of opposite parity, sorted by (c, a).

sum_of_four_squares

Every non-negative integer is a sum of four squares (Lagrange). Returns one representation n = a² + b² + c² + d² with a ≤ b ≤ c ≤ d, or None for negative n.

sum_of_two_squares

Write n ≥ 0 as a² + b² with 0 ≤ a ≤ b, if possible.