How to solve $100x +19 =0 \pmod{23}$ How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ?
In general I want to know how to solve $ax=b \pmod{c}$.
 A: Hint $\displaystyle\rm\,\ mod\ 23\!:\,\ x\,\equiv\, \frac{\color{brown}{-19}}{4\cdot \color{#0A0}{25}}
\,\equiv\,\frac{\color{brown}4}{4\cdot\color{#0A0} 2}
\,\equiv\, \frac{\color{blue}1}2
\,\equiv\, \frac{\color{blue}{24}}2
\,\equiv\, 12,\ \:$ 
by $\:\ \begin{array}{r}\color{brown}{{-}19\equiv 4}, & \color{blue}{1\equiv 24}\\ \color{#0A0}{25\equiv 2}\,\end{array} $
A: First, $100=4\cdot 23+8$, so $100\equiv 8\pmod{23}$. Then
$$
100x\equiv 8x\equiv -19\equiv 4\pmod{23}.
$$
Since $4$ and $23$ are coprime, $4$ is invertible in $\mathbb{Z}/23\mathbb{Z}$, ($\mathbb{Z}/23\mathbb{Z}$ is in fact a field), so multiplying by $4^{-1}$ yields $2x\equiv 1\pmod{23}$. Multiply both sides by $12$ to get $24x\equiv 12\pmod{23}$. But $24\equiv 1\pmod{23}$, so $x\equiv 12\pmod{23}$.
For the general solution to $ax\equiv b\pmod{c}$, it is a common theorem that $ax\equiv b\pmod{c}$ has a solution iff $d\mid b$ where $d=\gcd(a,c)$. When this is the case, the solutions form an arithmetic progression with common difference $c/d$, for a total of $d$ solutions modulo $c$. You can read about this for instance as Theorem 2.17, page 62, of Ivan Niven's Introduction to the Theory of Numbers in the Section "Solutions to Congruences."
A: $$ x \equiv \frac{-19}{100} \equiv \frac{4}{100} \equiv \frac{1}{25} \equiv \frac{1}{2} \equiv \frac{ 12}{24} \equiv 12.$$
A: A related problem. First step we simplify the congruence as
$$ 100 x \equiv -19({\rm mod}\, 23) \Rightarrow  8 x \equiv 4 ({\rm mod}\, 23) \,. $$
The last congruence follows from subtracting multiples of $23$ from 100 and adding $23$ to $-19$ which is allowed by the rules of congruences. We can simplify the last congruence further to
$$ 2 x \equiv 1 ({\rm mod}\, 23 ) \,.$$
since $ {\rm gcd}(4,23) = 1 \,.$
Now, since ${\rm gcd}( 2,23 )=1 \,, $ then the congruence has exactly one solution (this is a theorem) and by inspection you can see that $x=12$ is a solution.
Another Approach 
This is a technique can be used to solve linear congruences.,
if $ a x \equiv b({\rm mod}\, m) $, then you can reduce it to $ m y \equiv -b({\rm mod}\, a)\,.$ If $y_0$ is a solution for of the reduced congruence, then $x_0$ defined by 
$$ x_0 = \frac{my_0+b}{a} \,.$$
is a solution of the original congruence.
Applying this algorithm to your problem, we can reduce our congruence to 
$$ 23 y \equiv 19({\rm mod}\, 8) \Rightarrow 7 y \equiv 3({\rm mod}\, 8)\,. $$
You can see now by inspection that $y_0 = 5 $ is a solution of the last congruence. Substituting in 
$$  x_0 = \frac{m y_0 + b}{a} = \frac{23.5-19 - 19}{8}= 12\,. $$
Note that, you can repeat the same algorithm to the last congruence which results in a simpler congruence. If we do so, we get the following congruence
$$ z \equiv -3({\rm mod}\, 7) \,$$
such that 
$$ y_0 = \frac{m z_0 + b}{a} \,. $$ 
We can see by inspection that $z_0=4$ is a solution which implies 
$$ y_0= \frac{8.4+3}{7} = 5 \,$$
which what we got before.
A: $100x +19 =0 \pmod{23}$
$100x  ≡ -19 \pmod{23}$
$92x+8x=4-23\pmod{23}$
$=>8x≡4 \pmod{23}$ dividing both sides by $23$ and taking resdiues,
So,  $2x≡1 \pmod{23}$  dividing both sides by $4$ which is possible as $(4,23)=1,$
Now $\frac{23}{2}=11+\frac{1}{2}$  So, $23-2\cdot 11=1$
(Please refer to this  and this, for the theorem used.)
So, $2x≡23-2\cdot 11 \pmod{23}=>2x≡-22\pmod{23}$
$x≡-11\pmod{23}$ dividing both sides by $2$ as $(2,23)=1$
$x≡-11\pmod{23}≡12\pmod{23}$
To solve the general problem, $ax≡b\pmod{c}$,
$d=(a,b)$ must divide $c$ to admit any solution(according to this or this).
If we divide either side by $d$, so that $Ax≡B\pmod{C}$  where $\frac{a}{A}=\frac{b}{B}=\frac{c}{C}=d$ and (A,B)=1.
Using convergent property of continued fraction, we can get integers $r,s$ such that $rA-sB=±1$
For example, $\frac{17}{13}=1+\frac{4}{13}=1+\frac{1}{\frac{13}{4}}=1+\frac{1}{3+\frac{1}{4}}$
So, the convergent here is $1+\frac{1}{3}=\frac{4}{3}$
So. $17\cdot 3 -  13\cdot 4$ must be $±1$ , and is $-1$.
Put $rA-sB$ with proper sign in place of $(1)$,  $Ax≡B(1)\pmod{C}$
One example can be found here.
Please refer to this for the details.
