# Find all solutions to linear congruences

Find all the solutions of each of the linear congruences below:

\begin{align} &(a) &10x &\equiv 5 \pmod{15},\\ &(b) &6x &\equiv 7 \pmod{26},\\ &(c) &7x &\equiv 8 \pmod{11}. \end{align}

I'm not entirely sure how to get these solutions by hand. I know how to prove there are solutions.

For example:

$(a) \quad\gcd(10,15)=5$ and we know $5|5$.

From there I set $10x+15y=5$ and divide through by $5$. Leaving us with $2x+3y=1$. I know some solutions for $x$ and $y$, such as $x=-1$ and $y=1$, but that's all I have thus far.

-
Do you know that $ax\equiv b\pmod{m}$ has solutions iff $\gcd(a,m)\mid b$, and the solutions form an arithemtic progression with difference $m/g$ for $g$ total solutions? – yunone Sep 26 '12 at 19:57
I think that is what I was trying to show for part $(a)$. I'm just not sure where to go afterward. – Swine.Flu Sep 26 '12 at 19:59
See here. – Mhenni Benghorbal Sep 26 '12 at 21:37

It seems like you're familiar with the theorem in the comments above. For part (a), by inspection, you can see that $x\equiv 2$ is a solution. Since $g=\gcd(10,15)=5$ and $m/g=15/5=3$, you know there are $5$ total solutions $\pmod{15}$, and the others are found just be adding $3$ successively until you've found all $5$.

For (b), $\gcd(6,26)=2$ but $2\nmid 7$, so how many solutions can there be?

Part (c) is nice because $7$ and $11$ are coprime, so $7$ is actually invertible here. Try to find $7^{-1}\pmod{11}$, and then multiply both sides of $7x\equiv 8\pmod{11}$ by it to find the unique solution for $x$ modulo $11$.

-
I'm following most for part $(a)$ except for a couple things. Do we know there are only $5$ solutions because the $gcd(10,15)=5$? And also, what do you mean adding $3$ successively? Adding $3$ to $x=2$? So you're saying $x=5$ and $x=8$ are also solutions? – Swine.Flu Sep 27 '12 at 0:00
@user42783 Yes, $\gcd(a,m)$ gives the total number of solutions of $ax\equiv b\pmod{m}$ provided $\gcd(a,m)\mid b$. By adding $3$ I mean just that, so $x\equiv 2,5,8,11,14$ are all solutions modulo $15$, which can be verified easily. – yunone Sep 27 '12 at 2:57

The second equation has no solution, as $6 x + 26 k$ is always even, and can never be 7.

-

If $\rm\:M\:|\:AX-B\:$ then $\rm\:D\:|\:M,A\:\Rightarrow\:D\:|\:B,\:$ so cancelling the maximal such $\rm\:D = gcd(M,A)\:$ yields

$$\rm M\:|\:AX-B\iff m\:|\:aX-b\quad for\ \ \ m\, =\, \frac{M}D,\,\ a\, =\, \frac{A}D,\,\ b \,=\, \frac{B}D$$

The latter equation has unique solution $\rm\: X \equiv b/a\pmod{m},\:$ since $\rm\:gcd(m,a)=1\:$ implies that $\rm\:a\:$ is invertible mod $\rm\,m\,$ by Bezout's Identity.

Finally note $\rm\ x\equiv c\pmod m\iff x\equiv c\!+\!m,\, c\!+\!2m,\ldots, c\!+\!Dm\pmod{Dm = M}$

-