Computing mod inverse?

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

• – user12859
Commented Oct 3, 2015 at 23:50
• 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$ Commented Oct 4, 2015 at 0:09
• What I linked you "to is the Extended Euclidean Algorithm which gives the" $\hspace{1.5 in}$ "coefficients of Bézout's identity". $\;$
– user12859
Commented Oct 4, 2015 at 0:14
• 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 Commented Oct 4, 2015 at 0:17
• No, you'll need either x or y, depending on which of {a,b} is to be inverted. $\;$
– user12859
Commented Oct 4, 2015 at 0:19

1 Answer

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.