$$341x \equiv 15 \pmod{912}$$
First, I found the GCD between $341$ and $912$ using Euclid's algorithm:
$$912 = 341 \cdot 2 + 230$$
$$341 = 230 \cdot 1 + 111$$
$$230 = 111\cdot2 + 8$$
$$111 = 8 \cdot 13 + 7$$
$$8 = 7\cdot 1 + 1$$
$$1 = 1\cdot1 + 0$$
Hence, GCD$(912, 341) = 1$. Then, per Bezout's identity, I rewrote $1$ as a linear product: $912p + 341q$.
We have that:
$$230 = 912 – 341 \cdot 2$$
$$111 = 341 – 230\cdot 1$$
$$8 = 230 – 111\cdot2$$
$$7 = 111 – 8\cdot13$$
$$1 = 8-7\cdot1$$
Therefore, $1 = 912\cdot43 – 341\cdot 115$.
This, as per my understanding (absolutely do tell me if I'm wrong) should mean that $115$ is the inverse of $341$ modulo $912$.
Therefore, here's what I did:
$$341x = 15 \pmod{912}$$
$$341 \cdot 115 x \equiv 1\cdot x \equiv 15\cdot 115 = 1725 \pmod{912}$$
$$x \equiv 1725 \pmod{912}$$
Now, subbing $1725$ for its remainder from the division by $912$, we have:
$$x = -99 \pmod{912}$$
However, the correct answer is $x \equiv 99 \pmod{912}$. What did I do wrong?
Best Answer
$$1=912\cdot43−341\cdot115$$ This is correct. However, this means that $-115$ is the inverse of $341$, since your expression should be of the form $1=ax+by$. Multiplying both sides by $-115$, you would get the correct answer.