
Originally Posted by
ThePerfectHacker
$\displaystyle 4871x \equiv 1 (\bmod 7642)$
Means,
$\displaystyle 7642|(4871x - 1)$
And this means,
$\displaystyle 4871x - 1 = 7642z$ for some $\displaystyle z\in \mathbb{Z}$.
This means,
$\displaystyle 4871x + 7642 y = 1$ where $\displaystyle y=-z$.
Let us find the smallest positive integral which solves this for $\displaystyle x$.
First use die Euclidean algorithm.
$\displaystyle 7642 = 1\cdot 4871 + 2771$
$\displaystyle 4871 = 1\cdot 2771 + 2100$
$\displaystyle 2771 = 1\cdot 2100 + 671$
$\displaystyle 2100 = 3\cdot 617 + 87$
$\displaystyle 617 = 7\cdot 87 + 8$
$\displaystyle 87 = 10\cdot 8 + 7$
$\displaystyle 8 = 1\cdot 7 + 1$
$\displaystyle 7 = 7\cdot 1 + 0$
Now continue.