**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

## No comments:

## Post a Comment