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.

I have been trying very hard to solve this type of congruence equation: $$ax = b \pmod n$$ and finally managed to actually solve a few by using properties like $$\text{if}\quad \begin{cases} ax=b \pmod n \\ cx=d \pmod n \end{cases} \quad\text{then}\quad acx = bd \pmod n$$ but still there are some simple congruences which I am not able to solve like $$25x=15\pmod{29}.$$

I tried to make use of both above and transitive property of congruences but that is not working here.

Now, I wanted to ask if is there any other method to solve congruences. I am asking this because I have very little knowledge of congruences. I have Burton's book of number theory and that helped me much better than Zuckerman's text did. But, still there are some topics that I am not able to do yet.

share|improve this question
    
It isn't true that $ax\equiv b,cx\equiv d\bmod n\implies acx\equiv bd$ mod $n$. Rather, it entails $acx^2\equiv bd$ mod $n$. Anyway, to solve $ax\equiv b$ mod $n$ when $\gcd(a,n)=1$, you multiply both sides by $a^{-1}$ to get $x\equiv a^{-1}b$ mod $n$, where $a^{-1}$ is the inverse. If $a$ and $n$ share a common factor then either $b$ does not share all of the same factors and the congruence has no solution, or you can use that $am\equiv bm$ mod $km$ entails $a\equiv b$ mod $k$ to take out common factors of the original congruence. –  anon Aug 18 '12 at 7:05
2  
Please see meta.math.stackexchange.com/questions/3399/… and consider accepting answers to some of your questions. –  Gerry Myerson Aug 18 '12 at 10:18
    
I answered a closely related question just yesterday, and linked to yet another closely related question that I had answered some time ago. See my answer below. I linked to that much earlier answer. It pretty much covers the situation when you're working modulo a prime number. –  Michael Hardy Aug 18 '12 at 16:05

3 Answers 3

up vote 1 down vote accepted

Hint $\ $ Since $\rm\,gcd(25,29) = 1,\:$ Bezout $\rm\:\Rightarrow\:1/25\:$ exists mod $\,29.\:$ Therefore

$$\rm mod\ 29\!:\,\ 25\,x\equiv 15\:\Rightarrow\:x\equiv \frac{15}{25}\equiv\frac{3}{5}\equiv\frac{3\cdot 6}{5\cdot 6}\equiv\frac{18}1$$

share|improve this answer
    
Bill, could I ask you a little thing in the chat? –  Pedro Tamaroff Aug 18 '12 at 14:43

$$25x\equiv 15\pmod{29}\tag{1}$$

$29$ is a prime number, an one can show (I think Gauss showed) that that implies every number in $\{1,2,3,\ldots,28\}$ must have a mod-$29$ multiplicative inverse within that set. So let's find the inverse $y$ of $25$, so that $25y\equiv1\pmod{29}$, and then multiply both sides of $(1)$ by $y$, getting $$ x\equiv15y\pmod{29}. $$ We want: $$ \begin{align} 25y & \equiv 1 \pmod {29} \\ 25y & = 1 - 29z \\ 25y+29z & = 1. \end{align} $$

If we divide $29$ by $25$, we get $1$, with remainder $4$: $$ 29-\{1\}25 = 4\tag{2} $$ Now divide $25$ by $4$, getting $6$, with remainder $1$: $$ 25-\{6\}4 = 1\tag{3} $$ Because $(2)$ is true, we can put $29-\{1\}25$ in place of $4$ in $(2)$: $$ 25-\{6\}(29-\{1\}25). $$ Now collect the $29$s and $25$s: $$ -\{6\}29 + \{7\}25 = 1.\tag{4} $$ So we have $y=7$ and $z=-6$.

Thus $(4)$ tells us that $$ 7\cdot25\equiv 1\pmod{29} $$

Thus multiply both sides of $(1)$ by $7$: $$ x\equiv7\cdot15\equiv 18 \pmod{29}. $$ See Calculating the Modular Multiplicative Inverse without all those strange looking symbols for the way to find the inverse of $322$ mod $701$. It turns out to be $455$.

share|improve this answer

A related problem. First step we simplify the congruence as $$ 25 x \equiv 15({\rm mod}\, 29) \Rightarrow 5 x \equiv 3 ({\rm mod}\, 29)\,, $$ since $gcd(5,29)=1\,.$

You can use the following algorithm,

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

$$ 29 y \equiv -3({\rm mod}\, 5) \Rightarrow 4 y \equiv -3({\rm mod}\, 5)\,. $$ You can see now by inspection that $y_0 = 3 $ is a solution of the last congruence. Substituting in $$ x_0 = \frac{my_0+b}{a}=\frac{29.3+3}{5}=18\,. $$

share|improve this answer

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.