Data Modelling & AI Data Structure & Algorithm

Find initial integral solution of Linear Diophantine equation if finite solution exists

21 June 2025

0

Given three integers a, b, and c representing a linear equation of the form: ax + by = c. The task is to find the initial integral solution of the given equation if a finite solution exists.

A Linear Diophantine equation (LDE) is an equation with 2 or more integer unknowns and the integer unknowns are each to at most degree of 1. Linear Diophantine equation in two variables takes the form of ax+by=c, where x,y are integer variables and a, b, c are integer constants. x and y are unknown variables.

Examples:

Input: a = 4, b = 18, c = 10
Output: x = -20, y = 5

Explanation: (-20)*4 + (5)*18 = 10

Input: a = 9, b = 12, c = 5
Output: No Solutions exists

Approach:

First, check if a and b are non-zero.
If both of them are zero and c is non-zero then, no solution exists. If c is also zero then infinite solution exits.
For given a and b, calculate the value of x₁, y₁, and gcd using Extended Euclidean Algorithm.
Now, for a solution to existing gcd(a, b) should be multiple of c.
Calculate the solution of the equation as follows:

x = x₁ * ( c / gcd )
y = y₁ * ( c / gcd )

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h> 
using namespace std;
 
// Function to implement the extended
// euclid algorithm
int gcd_extend(int a, int b,
               int& x, int& y)
{
    // Base Case
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else {
        int g = gcd_extend(b,
                           a % b, x, y);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
void print_solution(int a, int b, int c)
{
    int x, y;
    if (a == 0 && b == 0) {
 
        // Condition for infinite solutions
        if (c == 0) {
            cout
                << "Infinite Solutions Exist"
                << endl;
        }
 
        // Condition for no solutions exist
        else {
            cout
                << "No Solution exists"
                << endl;
        }
    }
    int gcd = gcd_extend(a, b, x, y);
 
    // Condition for no solutions exist
    if (c % gcd != 0) {
        cout
            << "No Solution exists"
            << endl;
    }
    else {
 
        // Print the solution
        cout << "x = " << x * (c / gcd)
             << ", y = " << y * (c / gcd)
             << endl;
    }
}
 
// Driver Code
int main(void)
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
static int x, y; 
 
// Function to implement the extended
// euclid algorithm
static int gcd_extend(int a, int b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        int g = gcd_extend(b, a % b);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
static void print_solution(int a, int b, int c)
{
    if (a == 0 && b == 0) 
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            System.out.print("Infinite Solutions " +
                             "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            System.out.print("No Solution exists" + 
                             "\n");
        }
    }
    int gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        System.out.print("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        System.out.print("x = " + x * (c / gcd) +
                       ", y = " + y * (c / gcd) + "\n");
    }
}
 
// Driver Code
public static void main(String[] args) 
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach 
import math
 
x, y = 0, 0
   
# Function to implement the extended
# euclid algorithm
def gcd_extend(a, b):
    global x, y
     
    # Base Case
    if (b == 0):
        x = 1
        y = 0
        return a
   
    # Recursively find the gcd
    else:
        g = gcd_extend(b, a % b)
        x1, y1 = x, y
        x = y1
        y = x1 - math.floor(a / b) * y1
        return g
   
# Function to print the solutions of
# the given equations ax + by = c
def print_solution(a, b, c):
    if (a == 0 and b == 0):
       
        # Condition for infinite solutions
        if (c == 0):
            print("Infinite Solutions Exist")
   
        # Condition for no solutions exist
        else :
            print("No Solution exists")
    gcd = gcd_extend(a, b)
   
    # Condition for no solutions exist
    if (c % gcd != 0):
        print("No Solution exists")
    else: 
        # Print the solution
        print("x = ", int(x * (c / gcd)), ", y = ", int(y * (c / gcd)), sep = "")
         
# Given coefficients
a = 4
b = 18
c = 10
 
# Function Call
print_solution(a, b, c)
 
# This code is contributed by decode2207.

C#

// C# program for the above approach
using System;
 
class GFG{
 
static int x, y; 
 
// Function to implement the extended
// euclid algorithm
static int gcd_extend(int a, int b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        int g = gcd_extend(b, a % b);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
static void print_solution(int a, int b, int c)
{
    if (a == 0 && b == 0) 
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            Console.Write("Infinite Solutions " +
                          "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            Console.Write("No Solution exists" + 
                          "\n");
        }
    }
    int gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        Console.Write("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        Console.Write("x = " + x * (c / gcd) +
                    ", y = " + y * (c / gcd) + "\n");
    }
}
 
// Driver Code
public static void Main(String[] args) 
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function call
    print_solution(a, b, c);
}
}
 
// This code contributed by amal kumar choubey

Javascript

<script>
 
// Javascript program for the above approach 
  
let x, y; 
 
// Function to implement the extended
// euclid algorithm
function gcd_extend(a, b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        let g = gcd_extend(b, a % b);
        let x1 = x, y1 = y;
        x = y1;
        y = x1 - Math.floor(a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
function print_solution(a, b, c)
{
    if (a == 0 && b == 0) 
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            document.write("Infinite Solutions " +
                             "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            document.write("No Solution exists" + 
                             "\n");
        }
    }
    let gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        document.write("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        document.write("x = " + x * (c / gcd) +
                       ", y = " + y * (c / gcd) + "<br/>");
    }
}
 
// Driver Code
     
   let a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c); 
         
</script>

Output:

x = -20, y = 5

Time Complexity: O(log(max(A, B))), where A and B are the coefficient of x and y in the given linear equation.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Find initial integral solution of Linear Diophantine equation if finite solution exists

C++

Java

Python3

C#

Javascript

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

Beyond Context Overload: How Parlant × Milvus Brings Control and Clarity to LLM Agent Behavior

Understanding IVF Vector Index: How It Works and When to Choose It Over HNSW

LEAVE A REPLY Cancel reply

Most Popular

Google Gemini learns a new trick using reference images for Veo 3.1 video creations

Vine gets a reboot that prioritizes human-made videos

Google Play Store makes it easier to find the shows you’re looking for

Divine debuts as the new Vine, reviving the popular six-second short videos

EDITOR PICKS

Google Gemini learns a new trick using reference images for Veo 3.1 video creations

Vine gets a reboot that prioritizes human-made videos

Google Play Store makes it easier to find the shows you’re looking for

POPULAR POSTS

Google Gemini learns a new trick using reference images for Veo 3.1 video creations

Vine gets a reboot that prioritizes human-made videos

Google Play Store makes it easier to find the shows you’re looking for

POPULAR CATEGORY

ABOUT US

FOLLOW US