0
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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)$) $\endgroup$ – player3236 Mar 5 at 17:12
1
$\begingroup$

The second row is $5 = 1\cdot 3 + 2$ and the third one, $3 = 1\cdot 2 + 1$.

From here you have to calculate backwards.

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

$\endgroup$

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