Diophantine Equation Calculator

Solve Diophantine Equation \(Ax + By = C\)





Formula

The Diophantine equation is of the form:

\[ Ax + By = C \]

Where:

Example

Let's say the coefficients and constant are \( A = 15 \), \( B = 25 \), and \( C = 100 \). Using the Extended Euclidean Algorithm:

\[ 15x + 25y = 100 \]

We find the gcd of 15 and 25, which is 5. Since 100 is divisible by 5, integer solutions exist. The particular solution can be found as:

\[ x = 4, y = -2 \]

So, the general solution is:

\[ x = 4 + k \cdot 5, y = -2 - k \cdot 3 \quad \text{for any integer } k \]

What is a Diophantine Equation?

A Diophantine equation is an equation of the form \(Ax + By = C\) where \( A \) and \( B \) are coefficients, \( C \) is a constant term, and \( x \) and \( y \) are variables that take integer values. To solve the Diophantine equation, one must find integer solutions for \( x \) and \( y \) that satisfy the equation. This is typically done using the Extended Euclidean Algorithm to find the greatest common divisor (gcd) of \( A \) and \( B \) and then determining if \( C \) is divisible by the gcd. If it is, the equation has integer solutions.