2
$\begingroup$

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.

  • 0
    See [here](http://math.stackexchange.com/questions/186674/how-to-solve-100x-19-0-pmod23/186702#186702).2012-09-26

3 Answers 3

2

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

  • 1
    @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.2012-09-27
0

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

0

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