Take the 2-minute tour ×
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.

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|improve this question
    
Can anyone suggest the General solution for this type of equation –  Rahul Taneja Aug 25 '12 at 9:15
1  
I'd say mandatory reading material here: Modular multiplicative inverse. –  user2468 Aug 25 '12 at 14:34
add comment

5 Answers 5

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|improve this answer
add comment

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|improve this answer
add comment

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

share|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
2  
@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
add comment

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|improve this answer
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.