How to solve $100x +19 =0 \pmod{23}$

Question

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}$.

Answer 1

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{4\cdot 3}{\color{blue}{4\cdot 2\cdot 3}}\, \equiv\, \frac{12}{\color{blue}1}\ \:$ by $\:\ \color{brown}{{-}19\equiv 4},\ \color{#0A0}{25\equiv 2},\ \color{blue}{24\equiv 1}.$

Answer 2

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."

Answer 3

$$ x \equiv \frac{-19}{100} \equiv \frac{4}{100} \equiv \frac{1}{25} \equiv \frac{1}{2} \equiv \frac{ 12}{24} \equiv 12.$$

Answer 4

$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.

Answer 5

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.