Back to Number Theory Dsa

Diophantine Equations & Continued Fractions

September 22, 2026 Wasil Zafar 8 min read

Use constructive integer methods for equations and best approximations.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

A Diophantine equation requires integer solutions. For example, $3x+5y=17$ has $(x,y)=(4,1)$, whereas $6x+10y=17$ has no integer solution because the left side is always even. In general, $ax+by=c$ is solvable exactly when $\gcd(a,b)$ divides $c$.

Continued fractions answer a related discrete question: which rational numbers approximate a target well while keeping the denominator small? The expansion

$$ [a_0;a_1,\ldots,a_t]=a_0+\cfrac{1}{a_1+\cfrac{1}{\ddots+\cfrac{1}{a_t}}} $$

has convergents $p_i/q_i$ generated by

$$ p_i=a_ip_{i-1}+p_{i-2},\qquad q_i=a_iq_{i-1}+q_{i-2}. $$

For $415/93=[4;2,6,7]$, the convergents are $4/1$, $9/2$, $58/13$, and $415/93$. Consecutive convergents satisfy $p_iq_{i-1}-p_{i-1}q_i=(-1)^{i-1}$, so each fraction is reduced. For an irrational target $\alpha$, convergents satisfy the characteristic bound

$$ \left|\alpha-\frac{p_i}{q_i}\right|\lt\frac{1}{q_i^2}. $$

Quadratic irrationals have eventually periodic continued fractions. For positive nonsquare $D$, the periodic expansion of $\sqrt D$ yields solutions of Pell's equation $x^2-Dy^2=1$. For $D=2$, $(x,y)=(3,2)$ works because $3^2-2\cdot2^2=1$.

Continued fractions are an exact Euclidean-algorithm process, not a floating-point heuristic. Maintain integer recurrences and verify identities exactly; Pell's equation requires positive nonsquare $D$, while $ax+by=c$ requires $\gcd(a,b)\mid c$.

ConceptDefinition or notationExampleBoundary or non-exampleQuestion answered
Diophantine equationEquation with required integer solutions$3x+5y=17$A real solution alone is insufficientWhich discrete configurations work?
Linear solvability$\gcd(a,b)\mid c$$6x+10y=14$ is solvable$6x+10y=17$ is notDoes an integer solution exist?
Continued fraction$[a_0;a_1,\ldots]$$415/93=[4;2,6,7]$A finite expansion ending in $1$ is noncanonicalHow is Euclidean division encoded?
Convergent$p_i/q_i=[a_0;\ldots,a_i]$$58/13$ approximates $415/93$Decimal truncation need not be a convergentWhich small-denominator approximation is strong?
Approximation boundConvergent error is below $1/q_i^2$Accuracy improves rapidly with $q_i$Not every fraction satisfies the convergent guaranteeHow is error controlled?
Pell equation$x^2-Dy^2=1$$(3,2)$ for $D=2$Square $D$ has no positive solution with $y\gt0$Which quadratic integer pairs exist?
Fundamental solutionLeast positive Pell solution by $x$$(2,1)$ for $D=3$Later generated solutions are not fundamentalWhich pair generates the family?
Constrained familyParameterized solutions filtered by boundsRequire $0\le x,y\le100$Unbounded enumeration never terminatesWhich feasible solutions meet limits?

Step-by-Step Derivations and Algorithms

For a rational input $n/d$ with $d\gt0$, Euclidean division repeatedly writes $n=ad+r$, appends $a$, and replaces $(n,d)$ by $(d,r)$. The nonnegative remainder strictly decreases, so the process terminates. Folding the coefficients through the convergent recurrence reconstructs the reduced fraction.

For a nonsquare $D\gt0$, compute $a_0=\lfloor\sqrt D\rfloor$ using an integer square root. Starting from $m_0=0$, $d_0=1$, update

$$ m_{i+1}=d_i a_i-m_i,\qquad d_{i+1}=\frac{D-m_{i+1}^2}{d_i},\qquad a_{i+1}=\left\lfloor\frac{a_0+m_{i+1}}{d_{i+1}}\right\rfloor. $$

Feed each $a_i$ into the convergent recurrence. The first pair satisfying $p_i^2-Dq_i^2=1$ is the fundamental Pell solution.

For $ax+by=c$, extended Euclid supplies $au+bv=g$, where $g=\gcd(a,b)$. If $g\mid c$, scale to $x_0=u(c/g)$ and $y_0=v(c/g)$. Every solution is

$$ x=x_0+\frac bg t,\qquad y=y_0-\frac ag t,\qquad t\in\mathbb Z. $$

Bounds on $x$ and $y$ therefore become exact integer bounds on the single parameter $t$.

Diophantine Equations & Continued Fractions algorithm map
flowchart TD
    A["Classify the integer problem"] --> B{"Linear equation or approximation?"}
    B -->|"Linear"| C["Extended Euclid and divisibility test"]
    C --> D["Parameterize all solutions"]
    D --> E["Intersect bounds on t"]
    B -->|"Approximation"| F{"Rational or square root?"}
    F -->|"Rational"| G["Euclidean quotients"]
    F -->|"Square root"| H["Periodic integer state"]
    G --> I["Generate convergents"]
    H --> I
    I --> J["Verify exact target identity"]

The convergent invariant is $p_iq_{i-1}-p_{i-1}q_i=(-1)^{i-1}$, proving reduction and supporting approximation guarantees. Rational expansion takes $O(\log\min(|n|,d))$ Euclidean steps; Pell search uses constant state per term, although its exact integers may grow large.

Implementation, Complexity and Engineering

The reference implementation uses integer arithmetic throughout. It normalizes rational denominators, streams convergents, rejects square Pell parameters, and converts linear bounds to exact floor and ceiling constraints instead of trusting floating-point rounding.

from math import isqrt
from typing import Iterable


def continued_fraction(numerator: int, denominator: int) -> list[int]:
    if denominator == 0:
        raise ZeroDivisionError("denominator must be nonzero")
    if denominator < 0:
        numerator, denominator = -numerator, -denominator
    result = []
    while denominator:
        quotient, remainder = divmod(numerator, denominator)
        result.append(quotient)
        numerator, denominator = denominator, remainder
    return result


def convergents(coefficients: Iterable[int]):
    p2, p1, q2, q1 = 0, 1, 1, 0
    for coefficient in coefficients:
        p = coefficient * p1 + p2
        q = coefficient * q1 + q2
        yield p, q
        p2, p1, q2, q1 = p1, p, q1, q


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    old_r, r = abs(a), abs(b)
    old_x, x, old_y, y = 1, 0, 0, 1
    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_x, x = x, old_x - quotient * x
        old_y, y = y, old_y - quotient * y
    return old_r, old_x if a >= 0 else -old_x, old_y if b >= 0 else -old_y


def solve_linear_diophantine(a: int, b: int, c: int):
    if a == 0 and b == 0:
        if c == 0:
            raise ValueError("infinitely many unconstrained pairs")
        return None
    g, x, y = extended_gcd(a, b)
    if c % g:
        return None
    scale = c // g
    return x * scale, y * scale, b // g, -a // g


def fundamental_pell(d_value: int, max_steps: int = 1_000_000):
    if d_value <= 0:
        raise ValueError("D must be positive")
    root = isqrt(d_value)
    if root * root == d_value:
        raise ValueError("D must not be a square")
    m_value, denominator, coefficient = 0, 1, root
    p2, p1, q2, q1 = 0, 1, 1, 0
    for _ in range(max_steps):
        p = coefficient * p1 + p2
        q = coefficient * q1 + q2
        if p * p - d_value * q * q == 1:
            return p, q
        p2, p1, q2, q1 = p1, p, q1, q
        m_value = denominator * coefficient - m_value
        denominator = (d_value - m_value * m_value) // denominator
        coefficient = (root + m_value) // denominator
    raise RuntimeError("step limit reached")


if __name__ == "__main__":
    coefficients = continued_fraction(415, 93)
    assert coefficients == [4, 2, 6, 7]
    assert list(convergents(coefficients)) == [
        (4, 1), (9, 2), (58, 13), (415, 93)
    ]
    assert continued_fraction(-7, 3) == [-3, 1, 2]
    assert fundamental_pell(2) == (3, 2)
    assert fundamental_pell(13) == (649, 180)
    family = solve_linear_diophantine(6, 10, 14)
    assert family is not None
    x0, y0, dx, dy = family
    for parameter in range(-5, 6):
        assert 6 * (x0 + dx * parameter) + 10 * (y0 + dy * parameter) == 14
    assert solve_linear_diophantine(6, 10, 17) is None
    try:
        fundamental_pell(9)
        raise AssertionError("square D was accepted")
    except ValueError:
        pass
    print("all tests passed")
MethodTime profileSpaceNumeric riskFailure modeMitigation
Rational continued fraction$O(\log\min(\lvert n\rvert,d))$ divisions$O(L)$ coefficientsLarge integersZero denominatorReject before expansion
Streaming convergents$O(L)$ updates$O(1)$ excluding outputGrowing numerators and denominatorsWrong recurrence initializationTest determinant and reconstruction
Decimal approximationPrecision-dependentPrecision-dependentRounding changes decisionsMissing a boundary optimumPrefer exact fractions
Linear Diophantine family$O(\log\min(\lvert a\rvert,\lvert b\rvert))$$O(1)$Signed division errorsIgnoring gcd divisibilityNormalize and verify the equation
Bounded parameter searchEuclid plus output sizeOutput-dependentIncorrect endpointsBrute-forcing a large rectangleIntersect exact parameter bounds
Pell via continued fractionsOne update per term$O(1)$ stateSolutions can have many digitsFloating-point square rootUse isqrt and verify exactly
Brute-force Pell searchPotentially enormous$O(1)$Impractical runtimeTreating a cutoff as impossibilityUse periodic continued fractions

Applications, Case Studies and Exercises

Continued fractions provide exact rate conversion when hardware limits the denominator. Pell equations model repeated near-square relationships; after finding the fundamental solution $(x_1,y_1)$, further positive solutions satisfy

$$ x_k+y_k\sqrt D=(x_1+y_1\sqrt D)^k. $$

Practice

Apply Diophantine Equations & Continued Fractions

Case study 1 — constrained gear ratio. Approximate $415/93$ under denominator limits $Q=10$ and $Q=20$. Generate $[4;2,6,7]$. The last convergents within the limits are $9/2$ and $58/13$. Compare errors exactly using $|415q-93p|/(93q)$ rather than decimals.

Case study 2 — Pell arrangements. Solve $x^2-2y^2=1$. The expansion of $\sqrt2$ produces $(3,2)$ first. Square $3+2\sqrt2$ to obtain $17+12\sqrt2$, then verify $17^2-2\cdot12^2=1$.

Hands-on challenge. Build an exact approximation service accepting $n,d,Q$ and returning a reduced fraction with denominator at most $Q$. Add a Pell endpoint for nonsquare $D$. Test negative numerators, $Q=1$, exact representation, square $D$, and $D\in\{2,3,5,13,61\}$. Success requires agreement with exhaustive rational search for every $Q\le100$ and exact Pell verification.

Tiered exercises. (1) Expand $43/19$. (2) Prove the determinant identity by induction. (3) Parameterize $15x+21y=6$. (4) Restrict its solutions to $0\le x,y\le100$. (5) Solve $x^2-3y^2=1$. (6) Debug code using int(D ** 0.5). (7) Extend the solver to $x^2-Dy^2=-1$.

Use extended Euclid for linear integer equations, continued fractions for exact approximation structure, and periodic square-root expansions for Pell equations. Never infer impossibility from a finite brute-force search or let floating-point rounding decide an integer identity.

Next in the Series

In Quadratic Residues & Modular Roots, we'll explore Determine and construct modular roots..

Continue the Series

GCD, LCM & Linear Diophantine Equations

Turn Bézout identities into constructive algorithms.

Read Article