My question is to do with the incongruent solutions of a linear congruence. This is the problem:

Find all integer solutions to the linear congruence $15x \equiv 36 \mod 57$.

I'm able to use Euclid's algorithm, the gcd etc to solve the linear Diophantine equation and get a general solution for $x$. I get $x=48+19t$ with $t\in\mathbb{Z}$.

Now I am required to express my answer as a linear congruence: So from the above it follows that $x \equiv 48 \mod 19 $.

However, I don't understand the next steps and would appreciate an explanation.

Notes then go on to say "now express your answer in the same modulus as the question (i.e., $57$). If we vary $t (=-2,-1,0,1,2)$ we find solutions $10,29,48,67$. But $67\equiv10 \mod 57$ and thus after $10,29,48$ we get no new solutions mod 57."

My questions are to do with the statement in bold:

Why does $67\equiv 10 \mod 57$ imply that we would get no new solutions? Also, why are there only $3$ incongruent solutions?

(I cooked up a sort of rough explanation, but it doesn't exactly satisfy me: $x=10,29,48,67,86$ etc depending on the value if $t$ we choose. But as $19(3)$ every $3$ solutions from $10,29,48$ will be equivalent to adding $3(19)=57$ (or a multiple of $57$) to one of $10,29,48$ and thus all the 'new' solutions will be equivalent to the original three solutions mod $57$.)

  • 2
    $\begingroup$ The residue class $48\pmod{19}$ (which BTW is the same as $10\pmod{19}$) splits into $57/19=3$ residue classes modulo $57$: namely, $10\pmod{57}$, $29\pmod{57}$, and $48\pmod{57}$. The residue class $67\pmod{57}$ is identical to the residue class $10\pmod{57}$. $\endgroup$ – W-t-P Jan 5 at 11:18

$48\equiv 10\pmod{\!19}\,$ so $\,x = 10 + 19\,\color{#c00}k.\,$ Division $\,k\div 3\,\Rightarrow\,\color{#c00}{k =\color{#0a0} r+3n}\ $ for $\, \color{#0a0}{r\in \{0,1,2\}}$

$\begin{align}{\rm Substituing\,\ we\ find }\ \ \ x &= 10+19(\color{#c00}{\color{#0a0}r\!+\!3n})\\ &= 10+19\,\color{#0a0}r+57n\\ &= 10+19\color{#0a0}{\{0,1,2\}}\! + 57n\\ &= \{10,29,48\} + 57n \end{align}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.