# Solving Linear Congruences with Euclidean algorithm

I have the following equation: $70x \equiv 2 \pmod {58}$ and this equation: $X = X_i + i \times \frac{n}{d}$.

Using the table method with Euclidean algorithm I do $6$ steps to find out $\rm{gcd}(70,58) = d = 2\quad\quad$ I know that $n = 58$ however what are $X_i$ & $i$.

How do I solve this equation ?

I assumed $X_i$ was denominator at step $i$ and $i$ was the number of step where the Euclidean algorithm ended. Seems I am wrong.

• It's even easier to write in mathjax than in whatever you were writing in, just $X_i$ instead of X[sub]i[/sub] or whatever you were using :). – So many hats Nov 3 '15 at 3:35

$X_i$ is any solution to the linear congruence $70x≡2 (\mod 58)$, $n$ is 58 as you mentioned and $i$ is any integer.
Therefore, what the equation really means is that from any particular solution $X_i$, we can construct an infinite amount of solutions $X = X_i + \frac{i*n}{d}$, where $d = \gcd(a,m)$.
You can find that particular solution $X_i$ either by inspection (if there is a trivial or obvious value of x that would make the equation hold) or by the Extended Euclidean Algorithm.