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 ; Print all the answers ; Input ; Function Call
function ExtendedEuclidAlgo ( a , b ) { if ( a == 0 ) { return [ b , 0 , 1 ] ; } else { let x1 = 1 , y1 = 1 ; let gcdy = ExtendedEuclidAlgo ( b % a , a ) ; let gcd = gcdy [ 0 ] ; x1 = gcdy [ 1 ] ; y1 = gcdy [ 2 ] ; let y = x1 ; let x = y1 - Math . floor ( b / a ) * x1 ; return [ gcd , x , y ] ; } } function linearCongruence ( A , B , N ) { A = A % N ; B = B % N ; let u = 0 , v = 0 ; let person = ExtendedEuclidAlgo ( A , N ) ; let d = person [ 0 ] ; u = person [ 1 ] ; v = person [ 2 ] ; if ( B % d != 0 ) { document . write ( - 1 ) ; return ; } let x0 = ( u * ( B / d ) ) % N ; if ( x0 < 0 ) x0 += N ; for ( let i = 0 ; i <= d - 1 ; i ++ ) { let an = ( x0 + i * ( N / d ) ) % N ; document . write ( an + " " ) ; } } let A = 15 ; let B = 9 ; let N = 18 ; linearCongruence ( A , B , N ) ;