# Inverse number using gcd [duplicate]

If I want to find the inverse number of $$5$$ $$mod448$$ using $$gcd$$. I try to do like that:
$$448=89\cdot5+3$$
$$gcd(5,448)=gcd(89,3)$$
$$89=3\cdot29+2$$
$$gcd(89,3)=gcd(29,2)$$
$$1=29-2\cdot14$$
$$1=29-14\cdot(89-29\cdot3)$$
$$1=43\cdot29-14\cdot89$$
But here I don't know how to continue, maybe I have mistake...

• Actually the Euclidean algorithm asserts that $\gcd (5,448) = \gcd(5,3)$, not $\gcd(89,3)$. (To see this, check that you will run into a contradiction for $\gcd(14,3)$) – player3236 Mar 5 at 17:12

The second row is $$5 = 1\cdot 3 + 2$$ and the third one, $$3 = 1\cdot 2 + 1$$.
$$1 = 3 - 2 = 3 - (5-3) = 2\cdot 3 - 5 = 2\cdot (448 - 89\cdot 5) - 5 = 2\cdot 448 - 179\cdot 5$$.
From here you see that $$179\cdot 5\equiv 1\mod 448$$. So $$5^{-1}= 179$$ in $$\Bbb Z_{448}$$.