[Math] Find all solutions to linear congruences

elementary-number-theorynumber theory

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.

Best Answer

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

Related Question