# What are the methods of solving linear congruences?

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.

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

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

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

-

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

-

25x=15 (mod 29)

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

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

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

φ(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

x=15*7=105

105 mod 29=18