2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ There is something wrong here. In (a), $24$ is a multiple of $6$ which makes the question odd and the answers even. $\endgroup$
    – Henry
    Oct 16, 2012 at 16:03
  • $\begingroup$ Since $\rm\:8\equiv 2\pmod 6$ they are the same solution. $\endgroup$
    – Bill Dubuque
    Oct 16, 2012 at 16:43

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – student.llama
    Oct 16, 2012 at 16:23
  • $\begingroup$ @student.llama, From the 1st line of your comment, $6\mid 3x\implies 2\mid x$ $\endgroup$
    – lab bhattacharjee
    Oct 16, 2012 at 16:24
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .