Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Find all integer solutions to linear congruences:

\begin{align} &(a) &3x &\equiv 24 \pmod{6},\\ &(b) &10x &\equiv 18 \pmod{25},\\ \end{align}

What I have so far:

$$(a) \gcd(3,6)=3$$ And we know $3|24$ so there are $3$ solutions. By inspection we know that $x=8$ is a solution.

One, question I have is, even though $x=8$ is a solution, I can also see that $x=2$ is a solution, and among others. Does it matter which I choose, or do I randomly choose a solution I see? From here I'm a tad confused. I'm missing something very simple.

$$(b) \gcd (10,25)=5$$

And $5 \nmid 18$ so there are no solutions. Right?

share|cite|improve this question
There is something wrong here. In (a), $24$ is a multiple of $6$ which makes the question odd and the answers even. – Henry Oct 16 '12 at 16:03
Since $\rm\:8\equiv 2\pmod 6$ they are the same solution. – Bill Dubuque Oct 16 '12 at 16:43
up vote 1 down vote accepted

Using this, $(10,25)=5$ must divide $9$ to admit any solution, which is not, so there is no solution.

$3x\equiv 24\pmod 6\implies 2\mid x$ i.e., any even value(not only $8$) of $x$ will satisfy the 1st congruence.

So, the system of the linear congruence has no solution as the 2nd congruence is not solvable.

Alternatively, for the 2nd congruence, $10x-18=25y$ for some integer $y$,

So,$5(2x-5y)=18, \frac{18}5=2x-5y$ which is an integer, hence contradiction.

share|cite|improve this answer
So, for $(a)$ I see: $$\begin{align} & 3x &\equiv 0 \pmod{6},\\ & 3x &\equiv 6 \pmod{6},\\ & 3x &\equiv 12 \pmod{6},\\\end{align}$$ So, $x=0,2,4...$ Are the solutions. How would I say this on an exam? – student.llama Oct 16 '12 at 16:23
@student.llama, From the 1st line of your comment, $6\mid 3x\implies 2\mid x$ – lab bhattacharjee Oct 16 '12 at 16:24

In (a) you say there are three solutions. In fact you should say there are three, modulo $6$. These are $0$, $2$ and $4$, and so all even $x$ are solutions to the original expression.

In (b) you are correct. Clearly $10x$ is always a multiple of $5$ and numbers equivalent to $18 \pmod{ 25}$ never are.

share|cite|improve this answer

Your Answer


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.