ax + by = c
The code below shows how we can solve Diophantine equations with a sample equation :
7x - 9y = 3
DiophantineSolver.cs
class Program
{
static void Main()
{
int a = 7,
b = -9,
c = 3;
DiophantineSolver.DiophantineSolution solution = DiophantineSolver.ExtendedGcd(a, b, c);
Console.WriteLine(solution.ToString());
}
}
/// <summary>
/// Class containing methods to solve Diophantine equations using the Extended Euclidean Algorithm.
/// </summary>
class DiophantineSolver
{
/// <summary>
/// Struct to hold the solution of a Diophantine equation.
/// </summary>
public struct DiophantineSolution
{
/// <summary>
/// Indicates whether the equation has a solution.
/// </summary>
public bool IsSolvable { get; set; }
/// <summary>
/// X0, a articular solution for variable x, or null if no solution exists. Other solutions of X can be derived from this.
/// </summary>
public int? X0 { get; set; }
/// <summary>
/// Y0, a particular solution, or null if no solution exists. Other solutions of Y can be derived from this.
/// </summary>
public int? Y0 { get; set; }
/// <summary>
/// The coefficient of x in the equation.
/// </summary>
public readonly int A;
/// <summary>
/// The coefficient of y in the equation.
/// </summary>
public readonly int B;
/// <summary>
/// The constant term in the equation.
/// </summary>
public readonly int C;
/// <summary>D: The greatest common divisor gcd(a,b) = d</summary>
/// <remarks>Solutions to the Diophantine linear equation exists only if C|D: D is divisible by C.</remarks>
public readonly int? D;
/// <summary>
/// Initializes a new instance of the DiophantineSolution struct.
/// </summary>
/// <param name="isSolvable">Indicates whether the equation has a solution.</param>
/// <param name="x0">The x-coordinate of the particular solution.</param>
/// <param name="y0">The y-coordinate of the particular solution.</param>
/// <param name="a">The coefficient of x in the equation.</param>
/// <param name="b">The coefficient of y in the equation.</param>
/// <param name="c">The constant term in the equation.</param>
/// <param name="d">The d= gcd(a,b) greatest common divisor found for a and b</param>
public DiophantineSolution(bool isSolvable, int? x0, int? y0, int a, int b, int c, int d)
{
IsSolvable = isSolvable;
X0 = x0;
Y0 = y0;
A = a;
B = b;
C = c;
D = d;
}
/// <summary>
/// Returns a string representation of the solution.
/// </summary>
/// <returns>A string representation of the solution.</returns>
public override string ToString()
{
if (IsSolvable)
{
string result = $"""
Diophantine Linear Equation Solver result for equation
AX + BY = C
{A}x + {B}y = {C}
A={A}, B={B}, C={C}
Greatest common divisor :
d = gcd(a,b) = {D?.ToString() ?? "No gcd found"}
Solutions exists? {IsSolvable}, since d|c = {D}|{C}: {C} is divisible by {D}
Particular solution A(x0) + B(y0) = C
x0 = {X0}, y0 = {Y0}
({A}*{X0}) + ({B}*{Y0}) = {C}
({A * X0}) + ({B * Y0}) = {C}
Generalized solution:
{GetParameterizedSolution()}
Additional solutions:
""";
if (D > 0)
{
for (int t = 1; t <= 3; t++)
{
int xn = X0!.Value + (B / D!.Value) * t;
int yn = Y0!.Value - (A / D!.Value) * t;
result += $"\nSolution {t}: x = {xn}, y = {yn} (t = {t}) , since : ({xn}*{X0}) + ({yn}*{Y0}) = ({xn * X0}) + ({yn * Y0}) = {C}";
}
}
else {
result += "No additional solutions exists";
}
return result;
}
else
{
return $"Diophantine Linear Equation Solver result\nNo solution exists. d = gcd(a,b) = {D}. Solution exists if: {C}|{D}. This gives a remainder of {C % D} != 0. {C} is not divisible by {D}. C = {C} = n*D + r = ({C / D}*{D}) + {C % D}.";
}
}
/// <summary>
/// Returns the parameterized solution expression as a string.
/// </summary>
/// <returns>A string representation of the parameterized solution.</returns>
public string GetParameterizedSolution()
{
if (D == 0){
return "No solution exists, so there is not general parameterized solution";
}
string generalEquation = "x' = x_0 + (B/D), y' = y_0 - (A/D)";
return $"{generalEquation}{Environment.NewLine}x' = {X0} + ({B}/{D})t, y' = {Y0} - ({A}/{D})t, where t is any integer";
}
}
/// <summary>
/// Solves the Diophantine equation ax + by = c using the Extended Euclidean Algorithm.
/// </summary>
/// <param name="a">The coefficient of x.</param>
/// <param name="b">The coefficient of y.</param>
/// <param name="c">The constant term.</param>
/// <returns>A DiophantineSolution struct containing the solution.</returns>
public static DiophantineSolution ExtendedGcd(int a, int b, int c)
{
int X0, Y0;
int gcd = ExtendedGcd(a, b, out X0, out Y0);
if (c % gcd != 0)
{
return new DiophantineSolution(false, null, null, a, b, c, gcd);
}
else
{
int x = X0 * (c / gcd);
int y = Y0 * (c / gcd);
return new DiophantineSolution(true, x, y, a, b, c, gcd);
}
}
/// <summary>
/// Computes the greatest common divisor of a and b, and finds coefficients X0 and Y0 such that a*X0 + b*Y0 = gcd(a, b).
/// </summary>
/// <param name="a">The first integer.</param>
/// <param name="b">The second integer.</param>
/// <param name="X0">The coefficient of a in the linear combination.</param>
/// <param="Y0">The coefficient of b in the linear combination.</param>
/// <returns>The greatest common divisor of a and b.</returns>
private static int ExtendedGcd(int a, int b, out int X0, out int Y0)
{
if (b == 0)
{
X0 = 1;
Y0 = 0;
return a; // Base case: gcd(a, 0) = a
}
int X1, Y1;
int gcd = ExtendedGcd(b, a % b, out X1, out Y1); // Recursive call
X0 = Y1; // Back substitution: X0 = Y1
Y0 = X1 - (a / b) * Y1; // Back substitution: Y0 = X1 - (a / b) * Y1
return gcd; // Return the gcd
}
}
The extended Euclidean algorithm calculates the greatest common divisor and in the recursion also applies back substitution. The coefficients X0 and Y0 founds satisfy the equation :
(a · X0) + (b · Y0) = gcd(a, b)
That is, a linear combination of the original integers a and b equaling the gcd(a,b). The output of running the code shown above is:
Diophantine Linear Equation Solver result for equation
AX + BY = C
7x + -9y = 3
A=7, B=-9, C=3
Greatest common divisor :
d = gcd(a,b) = 1
Solutions exists? True, since d|c = 1|3: 3 is divisible by 1
Particular solution A(x0) + B(y0) = C
x0 = 12, y0 = 9
(7*12) + (-9*9) = 3
(84) + (-81) = 3
Generalized solution:
x' = x_0 + (B/D), y' = y_0 - (A/D)
x' = 12 + (-9/1)t, y' = 9 - (7/1)t, where t is any integer
Additional solutions:
Solution 1: x = 3, y = 2 (t = 1) , since : (3*12) + (2*9) = (36) + (18) = 3
Solution 2: x = -6, y = -5 (t = 2) , since : (-6*12) + (-5*9) = (-72) + (-45) = 3
Solution 3: x = -15, y = -12 (t = 3) , since : (-15*12) + (-12*9) = (-180) + (-108) = 3
So an example of a solution of the equation :
7x -9y = 3
Is:
x = 12, y = 9, since (7*12) - (9*9) = 84 - 81 = 3.
Note that once you have found a solution to a linear Diophantine equation, you can found infinite other solutions.
More formally:
Diophantine Equation (Linear) Definition and Solvability
A linear Diophantine equation is an equation of the form:
(a · x) + (b · y) = c
where a, b, and c are integers, and x and y are unknown integers.
Solvability
The linear Diophantine equation (a · x) + (b · y) = c has integer solutions if and only if the greatest common divisor (gcd) of a and b divides c. In mathematical notation:
d is gcd. d|c => gcd(a, b) | c
If gcd(a, b) divides c (it is common to use d to notify gcd as a short term notation), then there exist integer solutions x and y such that:
(a · x) + (b · y) = c
Otherwise, there are no integer solutions.
The following parameters can be used:
Please note that the Free tier of Azure AI Search is rather slow and seems to only allow queryes at a certain interval, it will suffice to just test it out. To really test it out in for example an Intranet scenario, the standard tier Azure AI search service is recommended, at about 250 USD per month as noted.
