1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 :). $\endgroup$ – So many hats Nov 3 '15 at 3:35
1
$\begingroup$

$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.

If you haven't seen the EEA, this post might help: What's the difference between the euclidean algorithm and the extended euclidean algorithm?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.