1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Your answer is correct, since

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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