Solving $xm\equiv k\bmod p$ for $x$ without linear search? Given $x, m, p, k \in \mathbb{N}$, is there a way to solve this equation without linear search?
$$x\cdot m\equiv k\bmod p$$
The numbers $m$, $p$ and $k$ are known, $p$ is prime, and $m \le p$, we have to find $x$. We can loop for $x = 0$ to $x=p - 1$ to find the answer, but, can we do it faster?
 A: If $m$ is not prime to $p$, then the congruence will not have a solution unless $k\equiv 0$ (mod $p$), in which case any $x$ solves the congruence.
Otherwise $m$ is invertible mod $p$, hence $x\equiv m^{-1}k$ (mod $p$) is the unique solution. $m^{-1}$ can be computed using the extended Euclidean algorithm, see for instance here.
A: If $m=p$ then $k$ must be zero and $x$ arbitrary. 
When $0\lt m \lt p$ $m$ is invertible and $$x=m^{-1}k \pmod k$$
The respective calculation depends on the concerned numbers (it could be easy or hard).
A: mx= k (mod p) is the same as mx= k+ np for some integer m.  That is equivalent to mx- pn= k, a "Diophantine equation".   That can be solved by using the "Euclidean division algorithm".  
For example, the equation 7x= 25 (mod 31) is the same as 7x= 25+ 31n or 7x- 31n= 25.  7 divides into 31 4 times with remainder 3: 31(1)- 7(4)= 3. 3 divides into 7 twice with remainder 1: 7(1)- 3(2)= 1.  Replacing "3" in that equation by "31(1)- 7(4)" gives 7(1)- 2(31(1)- 7(4))= 7(9)- 2(31)= 1.  Multiply both sides by 25 to get 7(225)- 31(50)= 25.  So one solution to 7x- 31n= 25 is x= 225, n= 50.  It easy to see that x= 225+ 31k, n= 50+ 7k is, for any k, also a solution: 7(225+ 31k)- 31(50+ 7k)= 7(225)- 31(50)+ 217k+ 217k= 25.
