Given three numbers $a, b$, and $n$, is it possible to find a number $k$ such that $ka\equiv b\pmod{n}$?

Question

I came up across this problem working on some (purely academic) attack on cryptographic schemes.

Given any three integers $a,b,n$ such that $a<n,b<n$, I am interested in an integer $k$ which satisfies $$ka \equiv b \pmod{n}$$

I know that such $k$ doesn't exist for all $a,b$. For example, there is no solution to $2k \equiv 3 \pmod{10}$. So, I am stuck at these

1. Under what condition does such a $k$ exist for any $(a,b)$?
2. If it does not, is there any probability or bounds? For example, $k$ exists only for $20\%$ $ (a,b)$ pairs.
3. In case such a $k$ exists, is it possible to calculate it 'efficiently'?

Any other relevant information about '$k$' will be equally appreciated.

Thanks in advance!

Answer 1

If $a$ is relatively prime to $n$, then yes, you can set $k \equiv ba^{-1} \pmod{n}$ where $a^{-1}$ is the inverse of $a$ modulo $n$.

To calculate $a^{-1}$ you can use the Euclidean algorithm to solve the Bézout equation $ax+ny = 1$. The $x$ that you'll find is the $a^{-1}$ you're looking for.