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.

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.

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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
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. –  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.

share|improve this answer

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

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.