# The incongruent solutions of a linear congruence

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

• 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}$. – 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}