Solving $ax + b = 0 \pmod{n}$ What is the most efficient algorithmic way of solving x in: $ax + b = 0 \pmod{n}$, where a, b, and n are extremely large integers?
A simple example:
$56473x + 36482 \equiv 0 \pmod{4536}$.
I find answers with examples particularly helpful.
 A: $$4536\mid 56473 x +36482 - 12\cdot 4536 x - 8\cdot 4536 = 2041x+194$$
so $2041x+194 = 4536y$ for some integer $y$. Thus $$2041|4536y-194 - 2\cdot 2041y = 454y-194 = 2(227y-97)$$
so $2041 \mid 227y-97$ and thus $227y-97 = 2041 z$ for some integer $z$. So we have: $$227\mid 2041z+97 - 9\cdot 227 z = 97-2z$$
Now we have $227t = 97-2z$ for some integer $t$ and thus $$2|-227t+97+228t-96 = t+1$$
So $t= 2s-1$ for some integer $s$. Now we go backward:
$$z=162-227s$$
$$y=1457-2041s$$
$$x= 3238-4536s$$
A: $ax+b\equiv 0\pmod m\iff x\equiv -ba^{-1}\pmod m$
When $\gcd(a,m)=1$ then $a^{-1}$ is ensured to exists and you can get it via the Extended Euclid algorithm
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
ExtendedEuclidAlgorithm(a,m) --> d,u,v

Where $\begin{cases}\gcd(a,m)=d\\au+mv=d\end{cases}$
So when $d=1$ then $au=1-mv\equiv 1\pmod m$ 
Meaning that $u\equiv a^{-1}\pmod m$

Let's apply it to your equation: $56473x+36482\equiv 0\pmod{4536}$
ExtendedEuclidAlgorithm(56473,4536) --> 1,1129,-14056

So the solutions are 
$x\equiv -36482\times 1129\equiv 3238\pmod{4536}$
