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.