What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) states that if m1, m2, ..., mk are pairwise coprime, then the system of congruences x = a1 (mod m1), x = a2 (mod m2), ..., x = ak (mod mk) has a unique solution modulo M = m1*m2*...*mk. This is used to solve systems of modular equations and has applications in cryptography (RSA) and computer science.

Diophantine Equation Solver • With Steps & Graph

What is a Diophantine Equation?

A Diophantine equation is a polynomial equation where only integer solutions are sought. Named after Diophantus of Alexandria (circa 250 AD), these equations are central to number theory. The simplest form is the linear Diophantine equation ax + by = c. A solution exists if and only if gcd(a,b) divides c. The extended Euclidean algorithm finds a particular solution, and the general solution is parameterized by an integer t.

Extended Euclidean Algorithm & Bezout's Identity

Bezout's identity states that for any integers a, b (not both zero), there exist integers x, y such that ax + by = gcd(a,b). The extended Euclidean algorithm constructively finds these Bezout coefficients. Starting from the standard Euclidean algorithm divisions, it back-substitutes to express gcd(a,b) as a linear combination of a and b. This gives a particular solution (x₀, y₀), and the general solution is x = x₀ + (b/d)t, y = y₀ − (a/d)t, where d = gcd(a,b).

Pell Equations & Continued Fractions

The Pell equation x² − Dy² = 1 (D positive, non-square) always has infinitely many solutions. The fundamental solution (smallest positive x₁, y₁) can be found via the continued fraction expansion of √D. All other solutions follow the recurrence x_n+1 = x₁x_n + Dy₁y_n, y_n+1 = x₁y_n + y₁x_n. Pell equations appear in approximating irrational numbers and in algebraic number theory.

Modular Arithmetic & Chinese Remainder Theorem

A linear congruence ax ≡ b (mod m) has solutions when gcd(a,m) divides b. The solution is found via the modular inverse of a, computed using the extended Euclidean algorithm. The Chinese Remainder Theorem (CRT) solves systems of congruences x ≡ a_i (mod m_i) when the moduli are pairwise coprime, giving a unique solution modulo the product of all moduli. CRT is foundational in cryptography (RSA), coding theory, and distributed computing.

Sums of Two Squares

Fermat's theorem on sums of two squares states that an odd prime p can be expressed as x² + y² if and only if p ≡ 1 (mod 4). More generally, a positive integer n is a sum of two squares if and only if every prime factor of the form 4k+3 appears to an even power in the factorization of n. Finding all representations x² + y² = n is a classic algorithmic problem solved by brute-force search or Cornacchia's algorithm.

Frequently Asked Questions

A Diophantine equation is a polynomial equation where only integer solutions are sought. Named after the ancient Greek mathematician Diophantus of Alexandria, these equations are fundamental in number theory. The simplest form is the linear Diophantine equation ax + by = c, where a, b, c are given integers and we seek integer x, y. Solutions exist if and only if gcd(a,b) divides c.

The extended Euclidean algorithm finds integers x and y such that ax + by = gcd(a,b). It extends the standard Euclidean algorithm by tracking the back-substitution. This gives a particular solution to ax + by = c (when gcd(a,b)|c), and the general solution is x = x₀ + (b/d)t, y = y₀ − (a/d)t for any integer t, where d = gcd(a,b).

Bezout's identity states that for any integers a and b (not both zero), there exist integers x and y such that ax + by = gcd(a,b). The extended Euclidean algorithm constructively finds these Bezout coefficients. This identity is the theoretical foundation for solving linear Diophantine equations and computing modular inverses.

The linear Diophantine equation ax + by = c has integer solutions if and only if gcd(a,b) divides c. If d = gcd(a,b) divides c, then there are infinitely many solutions parameterized by an integer t: x = x₀ + (b/d)t, y = y₀ − (a/d)t, where (x₀, y₀) is any particular solution found via the extended Euclidean algorithm.

A Pell equation is x² − Dy² = 1, where D is a positive non-square integer. It always has infinitely many solutions. The fundamental (smallest positive) solution can be found using continued fractions. All other solutions are generated by the recurrence x_n+1 = x₁x_n + Dy₁y_n, y_n+1 = x₁y_n + y₁x_n.

The Chinese Remainder Theorem (CRT) states that if m₁, m₂, …, m_k are pairwise coprime, then the system x ≡ a₁ (mod m₁), …, x ≡ a_k (mod m_k) has a unique solution modulo M = m₁·m₂·…·m_k. This is used to solve systems of modular equations and has applications in cryptography (RSA) and computer science.

The modular inverse of a modulo m is an integer x such that ax ≡ 1 (mod m). It exists if and only if gcd(a,m) = 1. You can find it using the extended Euclidean algorithm: solve ax + my = 1, then x (mod m) is the inverse. This calculator automatically computes modular inverses when solving congruences.

Yes, completely free with no registration or signup required. Features include: step-by-step extended Euclidean algorithm, Bezout identity computation, general parametric solutions, integer lattice point graphs, 4 equation types (linear, system, quadratic, modular), LaTeX export, PDF download, shareable URLs, and a built-in Python compiler with SymPy. All features are available without any paywall or usage limits.