# 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
Oct 3 '15 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$ Oct 4 '15 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
Oct 4 '15 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 Oct 4 '15 at 0:17
• No, you'll need either x or y, depending on which of {a,b} is to be inverted. $\;$
– user12859
Oct 4 '15 at 0:19

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