Find initial integral solution of Linear Diophantine equation if finite solution exists | Python3 program for the above approach ; Function to implement the extended euclid algorithm ; Base Case ; Recursively find the gcd ; Function to prlet the solutions of the given equations ax + by = c ; Condition for infinite solutions ; Condition for no solutions exist ; Condition for no solutions exist ; Print the solution ; Given coefficients ; Function Call
import math NEW_LINE x , y = 0 , 0 NEW_LINE def gcd_extend ( a , b ) : NEW_LINE INDENT global x , y NEW_LINE if ( b == 0 ) : NEW_LINE INDENT x = 1 NEW_LINE y = 0 NEW_LINE return a NEW_LINE DEDENT else : NEW_LINE INDENT g = gcd_extend ( b , a % b ) NEW_LINE x1 , y1 = x , y NEW_LINE x = y1 NEW_LINE y = x1 - math . floor ( a / b ) * y1 NEW_LINE return g NEW_LINE DEDENT DEDENT def print_solution ( a , b , c ) : NEW_LINE INDENT if ( a == 0 and b == 0 ) : NEW_LINE INDENT if ( c == 0 ) : NEW_LINE INDENT print ( " Infinite ▁ Solutions ▁ Exist " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ Solution ▁ exists " ) NEW_LINE DEDENT DEDENT gcd = gcd_extend ( a , b ) NEW_LINE if ( c % gcd != 0 ) : NEW_LINE INDENT print ( " No ▁ Solution ▁ exists " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " x ▁ = ▁ " , int ( x * ( c / gcd ) ) , " , ▁ y ▁ = ▁ " , int ( y * ( c / gcd ) ) , sep = " " ) NEW_LINE DEDENT DEDENT a = 4 NEW_LINE b = 18 NEW_LINE c = 10 NEW_LINE print_solution ( a , b , c ) NEW_LINE