2
$\begingroup$

How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great

$\endgroup$
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Extended_Euclidean_algorithm $\;$ $\endgroup$ – user12859 Oct 3 '15 at 23:50
  • $\begingroup$ What you linked me to is the Extended Euclidean Algorithm which gives the GCD (Greatest Common Divisor) of two numbers, no? It isn't helpful. I'm not looking for the GCD of these two numbers. I'm looking for an example similar to solve $x^{-1} \mod y$ $\endgroup$ – Shammy Oct 4 '15 at 0:09
  • 2
    $\begingroup$ What I linked you "to is the Extended Euclidean Algorithm which gives the" $\hspace{1.5 in}$ "coefficients of Bézout's identity". $\;$ $\endgroup$ – user12859 Oct 4 '15 at 0:14
  • $\begingroup$ I'm very confused. I thought it was rather simple to solve the problem I have. Are you saying I need to find the GCD(4,17) first? I just want to be clear $\endgroup$ – Shammy Oct 4 '15 at 0:17
  • 1
    $\begingroup$ No, you'll need either x or y, depending on which of {a,b} is to be inverted. $\;$ $\endgroup$ – user12859 Oct 4 '15 at 0:19
3
$\begingroup$

In order to compute the inverse of $a$ modulo $n$, use the extended Euclidean algorithm to find the GCD of $a$ and $n$ (which should be 1), together with coefficients $x,y$ such that $ax + ny = 1$. The inverse of $a$ modulo $n$ is thus $x$.

The extended Euclidean algorithm gives a constructive proof of Bézout's identity, which states that for all integers $a,b$ there exist integers $x,y$ such that $ax+by = \mathrm{gcd}(a,b)$. A different proof shows that the minimal positive value of $ax+by$ (over all $x,y$) is $\mathrm{gcd}(a,b)$.

The extended Euclidean algorithm works in greater generality, for any Euclidean domain. An important example is the ring of polynomials over a field.

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