Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
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.

share|cite|improve this answer

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

$100x ≡ -19 \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$


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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.