# euclidean algorithm iteration problem

So if I have a congruence of the form $ad \equiv 1 \mod m$, where $a$, $d$, $m$ are all integers and $m > a$, I should be able to find the integer $d$ satisfying the congruence using the Euclidean algorithm.

For example, $7d \equiv 1 \mod 30$ inserted into the Euclidean algorithm gives \begin{align*} 30 & = 4 \cdot 7 + 2\\ 7 & = 3 \cdot 2 + 1 \end{align*}

Working backwards gives \begin{align*} 1 & = 7 - 3 \cdot 2\\ & = 7 - 3(30 - 4 \cdot 7)\\ & = 13 \cdot 7 + (-3) \cdot 30 \end{align*}

[easily seen through some rearranging]

And so obviously $d = 13$, as $13 \cdot 7 = 1 \mod 30$ as desired.

I'm trying to execute this for $3d = 1 \mod 100$ But I always end up like this \begin{align*} A & = qB + r\\ 100 & = 33 \cdot 3 + 1\\ 1 & = 3 \cdot (-33) + 100 \cdot 1 \end{align*}

$d$ should turn out to be $67$, but I can't get to it. Help is appreciated

$$-33\equiv 67\mod 100$$