Inverse with Extended Euclidean Algorithm

cryptographyeuclidean-algorithmnumerical-calculus

I'm solving a task from https://www.coursera.org/learn/crypto/, particularly the following question:

enter image description here

I know that 3x – 5 = 0 and since "ax + b = 0" that implies "x = -b * a^-1", meaning we need to compute the inverse a^-1. Since a=3, we can compute inverse of it via two ways:

  • Formula: x^-1 = x^(p-2) mod p: 3^-1 = 3⁽19-2) mod 19 = 13

  • Extended Euclidean Algorithm: I'm not sure why I don't also get 13 when using this algorithm:

     19 = 3(6) + 1
 3 = 1(3) + 0

 therefore

 1 = 19 - 3(6)

    So the answer is 6, but that does not match 13 as above, which is the correct answer. Why doesn't Extended Euclidean Algorithm work when computing the inverse 3^-1?

Best Answer

Starting from where you ended: $1 = 19 - 3(6)$ implies that $-3(6) = 3(-6) \equiv 1 \pmod{19},$ so the modular inverse of $3$ is $-6 \equiv 13.$ We can double-check this with $3 \cdot 13 = 39 = 2(19) + 1 \equiv 1.$

In order to avoid this confusion in the future, it may help to write your final decomposition in the form of $ax + by = 1.$ Taking mods on both sides it should be clear that we have $ax \equiv 1 \pmod{y}$ and $by \equiv 1 \pmod{x},$ so $a \equiv x^{-1} \pmod{y}$ and $b \equiv y^{-1} \pmod{x}.$

Related Question