Solve Linear Congruences Ax = B ( mod N ) for values of x in range [ 0 , N | Java program for the above approach ; 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 ; Driver Code ; Input ; Function Call
import java . io . * ; class GFG { public static long [ ] ExtendedEuclidAlgo ( long a , long b ) { if ( a == 0 ) { return new long [ ] { b , 0 , 1 } ; } else { long x1 = 1 , y1 = 1 ; long gcdy [ ] = ExtendedEuclidAlgo ( b % a , a ) ; long gcd = gcdy [ 0 ] ; x1 = gcdy [ 1 ] ; y1 = gcdy [ 2 ] ; long y = x1 ; long x = y1 - ( long ) Math . floor ( b / a ) * x1 ; return new long [ ] { gcd , x , y } ; } } public static void linearCongruence ( long A , long B , long N ) { A = A % N ; B = B % N ; long u = 0 , v = 0 ; long person [ ] = ExtendedEuclidAlgo ( A , N ) ; long d = person [ 0 ] ; u = person [ 1 ] ; v = person [ 2 ] ; if ( B % d != 0 ) { System . out . println ( - 1 ) ; return ; } long x0 = ( u * ( B / d ) ) % N ; if ( x0 < 0 ) x0 += N ; for ( long i = 0 ; i <= d - 1 ; i ++ ) { long an = ( x0 + i * ( N / d ) ) % N ; System . out . print ( an + " ▁ " ) ; } } public static void main ( String [ ] args ) { long A = 15 ; long B = 9 ; long N = 18 ; linearCongruence ( A , B , N ) ; } }