Find $x$ for $b\equiv ax \pmod{p}$ for big numbers $a$, $b$ and $p$ How can the value $x$ be calculated, when $a$, $b$ and $p$ are given?
$$b\equiv ax  \pmod{p},$$
where $p$ is a big prime number, $a$ and $b$ are big numbers, that can be factorized.
 A: If $a$ is a multiple of $p$ but $b$ is not there is no solution, of course.
So I'm assuming you mean $a,b$ are not mulitples of $p$.  As $p$ is prime, this means $\gcd(a,p)$ and $\gcd(b,p) = 1$
By Bezoit's identity there are integers $m,n$ so that $am + pn = 1$.
Solve for those using Euclid's algorithrm.
(Let $p = k_1a + r_1$ and then $a= k_2r + r_2$ and the $r= k_3r_2 + r_3$ etc. )
Then $x = b*m$ will yield.
$a(b*m) = (am)*b= (1-pn)*b \equiv b \mod p$.
That's it.
Example:
If $a=54; b=36; p= 2017$
$2017 = k*54 + r= 37*54 + 19$
$54 = 2*19 + 16$
$19 = 16 + 3$
$16 = 3*5 + 1$
$1 = 16- 3*5$
$= 19 - 3 - 3*5= 19 - 3*6$
$= 19 - (19 - 16)*6 = -5*19 + 6*16$
$= -5*19 + 6(54-2*19)$
$=-17*19 + 6*54$
$= -17(2017 - 37*54) + 6*54$
$= -17*2017 + 635*54$
So $36 \equiv 36*1 \equiv 36*635*54 = 22860*54 \equiv 673*54 \mod 2017$.
A: You want $x\equiv b\cdot a^{-1}$. If you can factor $a$ and $b$, then this is the product of each factor of $b$ with the $\bmod p$ inverse of each factor of $a$. If $a$ and $b$ have any common factors, they will cancel.
