Inverse with Extended Euclidean Algorithm

euclidean-algorithm cryptography numerical-calculus

Solution 1:

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

Can the conjugate $\phi^{-1} \circ A \circ \phi$ be linear for nonlinear $\phi$?
Theorem 15.1 of Munkres Topology
Quadratic form for quartics
Finding a non-degenerated quadric containing three projective lines in $\mathbb{P}^3(\mathbb{C})$
Show $Q(x)\cdot Q(y)=x\cdot y\Rightarrow Q^TQ=I$
$\tan(z)=i$, no solution
How to isolate a variable inside floor and ceiling functions?
Integral inequality, proof verification
How to solve the nonlinear recurrence which depends on $n$
How to check if some equation can be solved using Lambert $\operatorname{W}$ function.
Prove that $\sum_{cyc}a^4b \ge \sum_{cyc} a^2$
Show that $M[x] \cong A[x] \otimes_{A} M.$