Solving Linear Congruences $a*x \equiv b\ (\textrm{mod}\ n)$

Note:   $(x,y)$ means $gcd(x, y)$
Given: $a,b,n$ and $(a,n)=1$
To find: $x$ such that $a*x \equiv b\ (\textrm{mod}\ n)$

This video explains how to solve this problem using extended gcd method.

Solution:
$\because (a, n) = 1$
$\therefore$ $1=M*a+N*n$ for some integers $M, N$.
Taking modulo $n$ on both sides,
$a*M\equiv 1\ (\textrm{mod}\ n)$
Simply multiply by $b$ on both sides,

$a*M*b\equiv b\ (\textrm{mod}\ n)$
$\therefore x=M*b$

Now problem is how to find $M,N$. We can use the Extended GCD Method as explained in the link. Following is the C++ implementation for the same.

Problem to practise: Prime Connection
Solution? Click here