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

-
Can anyone suggest the General solution for this type of equation – Rahul Taneja Aug 25 '12 at 9:15
I'd say mandatory reading material here: Modular multiplicative inverse. – user2468 Aug 25 '12 at 14:34

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

-

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

-

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

-
How did you get from (-19/100) to (4/100) and from (1/25 ) to (1/2) ??? – Khaled Aug 25 '12 at 9:50
@Khaled In mod 23, adding or subtracting multiples of 23 makes no difference to the value. So I added 23 to -19 to get 4, and subtracted 23 from 25 to get 2. – Ragib Zaman Aug 25 '12 at 9:52

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.

-

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

-
can you explain =>8x≡4(mod23) dividing both sides by 23, – Rahul Taneja Aug 25 '12 at 8:41
@RahulTaneja, could you please check the modified answer. – lab bhattacharjee Aug 25 '12 at 8:44
got your point. Thanks can you answer the second part of this question i.e. general solution – Rahul Taneja Aug 25 '12 at 8:47