Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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|cite|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
Please see… 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
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|cite|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|cite|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|cite|improve this answer

25x=15 (mod 29)

GCD (25,29)=1 => 1 solution

x=15/25=15*1/25 (mod 29)


φ(29)=28 =>

=> x=15*25^(φ(29)-1)=15*25^27 (mod 29)

25^2 (mod 29)=625=16

25^27 (mod 29)=(25^2)^13*25=16^13*25

16^2 (mod 29)=256=24

16^13*25 (mod 29)=(16^2)^6*16*25=24^6*400=24^6*23

24^2 (mod 29)=576=25

24^6*23 (mod 29)=(24^2)^3*23=25^3*23

25^2 (mod 29)=625=16

25^3*23 (mod 29)=25^2*25*23=16*25*23=368*25=20*25=500=7


105 mod 29=18

Answer: x=18

share|cite|improve this answer
Please use LaTeX syntax when posting answers! Also, usually it is better to not post answers when many answers already exist! – 6005 Jun 1 at 22:47

protected by Zev Chonoles Jun 1 at 22:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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