Solve Linear Congruences Ax = B ( mod N ) for values of x in range [ 0 , N | Function to stores the values of x and y and find the value of gcd ( a , b ) ; Base Case ; Store the result of recursive call ; Update x and y using results of recursive call ; Function to give the distinct solutions of ax = b ( mod n ) ; Function Call to find the value of d and u ; No solution exists ; Else , initialize the value of x0 ; Pr all the answers ; Input ; Function Call
def ExtendedEuclidAlgo ( a , b ) : NEW_LINE INDENT if a == 0 : NEW_LINE INDENT return b , 0 , 1 NEW_LINE DEDENT gcd , x1 , y1 = ExtendedEuclidAlgo ( b % a , a ) NEW_LINE x = y1 - ( b // a ) * x1 NEW_LINE y = x1 NEW_LINE return gcd , x , y NEW_LINE DEDENT def linearCongruence ( A , B , N ) : NEW_LINE INDENT A = A % N NEW_LINE B = B % N NEW_LINE u = 0 NEW_LINE v = 0 NEW_LINE d , u , v = ExtendedEuclidAlgo ( A , N ) NEW_LINE if ( B % d != 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT x0 = ( u * ( B // d ) ) % N NEW_LINE if ( x0 < 0 ) : NEW_LINE INDENT x0 += N NEW_LINE DEDENT for i in range ( d ) : NEW_LINE INDENT print ( ( x0 + i * ( N // d ) ) % N , end = " ▁ " ) NEW_LINE DEDENT DEDENT A = 15 NEW_LINE B = 9 NEW_LINE N = 18 NEW_LINE linearCongruence ( A , B , N ) NEW_LINE