congruence equations and inverse I got two questions that I'm wondering, one main question and one "bonus" question I guess

*

*what is the general method to solve congruence equations like $ax \equiv b \pmod m$?

Take for example $3x\equiv 2 \pmod 5$ how would I go about solving this?
I was able to solve it using trial and error and found the answer to be $4$, but I'm looking for a better and faster way to solve problems like these for larger $m$'s..
Also I'm wondering sometimes you can solve these with just the inverse of $a$, but when does that apply? only when $b=1$ and $a$ and $m$ are coprime? example $9x\equiv 1 \pmod 14$ for instance?


*can someone please show me how I can find the modular inverse of $9$  mod $14$? I'm familiar with the method used and I'm able to find the inverse in other examples, but I'm not sure why this one is causing me so much trouble, answer should be $11$ I think.

 A: For 1): if $a$ and $m$ are coprime, the extended Euclidean algorithm gives you an automatic way  to find the coeffcicients of a Bézout's relation:
$$ua+vm=1,\quad \lvert u\rvert<m,\enspace\lvert v\rvert< a$$
This Bézout's relation tells you $u$ is a modular inverse of $a$, hence
$$ax\equiv b\mod m\iff uax\equiv ub\mod m\iff x\equiv ub\mod m. $$
If $a$ and $m$ are not coprime, let $d=\gcd(a,m)$ and write $\;a=da'$, $m=dm'$ ($\gcd(a',m')=1$). The equation writes as
$$da'x\equiv b\mod dm',$$
and it has no solution if $b\not\equiv 0\mod d$. If $b=db'$, it is equivalent to 
$$a'x\equiv b'\mod m',$$
and we're back to the first case.
For 2), a Bézout's relation between $9$ and $14$ is $2\cdot 14-3\cdot 9=1$, hence
$$9^{-1}\equiv -3\equiv 11\mod 14. $$
A: A few methods to solve $ax\equiv b\pmod{m}$:
$1)\ $ Checking $x\equiv \{0,1,2,\ldots,m-1\}\pmod{m}$, i.e. using brute force.
$2)\ $ Doing something similar to this: $$3x\equiv 2\equiv -3\pmod{5}\stackrel{3}\iff x\equiv -1\equiv 4\pmod{5}$$
$$9x\equiv 1\equiv -27\pmod{14}\stackrel{:9}\iff x\equiv -3\equiv 11\pmod{14}$$
$3)\ $ Using inverses / Extended Euclidean Algorithm.
Inverses can always solve $ax\equiv b\pmod{m}$ when $\gcd(a,m)$. The solution is $x\equiv ba^{-1}\pmod{m}$.
You can find $a^{-1}\bmod m$ by either using Extended Euclidean Algorithm or solving $ax\equiv 1\pmod{m}$.
Using Extended Euclidean Algorithm:
$$\begin{array}\\14=14(1)+9(0)\\ 9=14(0)+9(1)\\ 5=14(1)+9(-1)\\4=14(-1)+9(2)\\1=14(2)+9(-3)\end{array}$$
Therefore $9^{-1}\equiv -3\equiv 11\pmod{14}$.

As for your comment: $ax\equiv b\pmod{m}$ has a solution if and only if $\gcd(a,m)\mid b$. This follows from Bézout's Lemma.
A: 1) $6\equiv1\mod5$ and thus $3*2\equiv1 \mod 5$ is the "inspection" route one could take there.
For, $9x\equiv1\mod14$, I could consider how $9\equiv-5\mod14$ where $-5*3\equiv-15\equiv-1\mod14$, so $3*9$ will give me a -1 so add another 3 and 9 together so that $9*3*3\equiv81\equiv11$ (14*5=70 would be the shortcut to see here) would seem to be the inverse which could be trimmed down by casting out 14s if doing this programmatically.
