# Solving a system of linear congruences in 2 variables

Given: $$6x+7y \equiv 17 \pmod{42} \tag1$$ $$21x+5y \equiv 13 \pmod{42} \tag2$$

Here's my initial attempt at solving the above system.

$(2) \times 35$: $$21x+7y \equiv 35 \pmod{42} \tag3$$ $(3)-(1)$: $$15x \equiv 18 \pmod{42}$$ $$5x \equiv 6 \pmod{14}$$ $$x \equiv 4 \pmod{14}$$ $$x \equiv 4,18,32 \pmod{42} \tag4$$ Substitute $(4)$ into $(2)$: $$5y \equiv 13 \pmod{42}$$ $$y \equiv 11 \pmod{42}$$ Hence the solutions in $\mathbb Z_{42}$ are $(4,11), (18,11), (32,11)$. I know this is correctly the solution set because the answers work, and because I've been told the system has 3 solutions.

Then I tried substituting $(4)$ into $(1)$, and also into $(3)$, and each time I got $$7y \equiv 35 \pmod{42}$$ $$7y \equiv 35 \pmod{42}$$ $$y \equiv 5,11,17,23,29,35,41 \pmod{42}$$ Now, I don't understand why substituting $(4)$ into $(1)$ (or $(3)$) instead of into $(2)$ created excess solutions. I would really appreciate it if someone could take a look and explain it to me..thanks!

-

Equation 1. and 3. don't give you enough information to identify $y$, since you can only solve for the expression $7y$ and $7$ isn't a unit modulo $42$.
Just to be sure: do you mean that eqn 2 works because $gcd(5,42)=1$, whereas eqns 1 & 3 fail because $gcd(7,42)\neq 1$? –  Ryan Aug 18 '12 at 15:34
@Ryan Right, equation 2. can be written as $y = 21x + 11 (\bmod 42)$ while 1. and 3. only determine $7y$, and therefore $y$ only up to a multiple of $6$, as you can see from your set of candidates. This is really because $7*6 = 42$. –  Cocopuffs Aug 18 '12 at 15:39
How did you get $y=21x+11 \pmod{42}$?? Assuming that you are basically just saying that the coefficient of $y$ (which we want to solve for) needs to be coprime with $42$, then my follow-up question is: what if the neither of the two coefficients of $y$ in the given system had been coprime with $42$? –  Ryan Aug 18 '12 at 16:00
@Ryan I multiplied both sides by $17$. If neither of the two coefficients had been coprime, you would only be able to determine $y$ up to $\bmod 6$ and would have more solutions $\bmod 42$. –  Cocopuffs Aug 18 '12 at 16:14
Oh heehee yes of course. Thanks. But I still don't understand how my multiplying Eqn 2 by $35$ created more solutions (after all, I had made sure to go back to $\mathbb Z_{42}$ immediately after multiplying Eqn 2 by $35$). I had originally thought that Eqns 2 and 3 were equivalent to each other (just like when solving regular simultaneous eqns). Without this intuition/understanding, do I then just have to be very careful in the final step and make sure that the eqn I choose to solve for $y$ contains the $y$-coefficient that has the lowest gcd with $42$ among all the available eqns?? –  Ryan Aug 18 '12 at 16:47