3
$\begingroup$

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!

1 Answers 1

2

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

  • 0
    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$?2012-08-18
  • 0
    @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$.2012-08-18
  • 0
    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$?2012-08-18
  • 0
    @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$.2012-08-18
  • 0
    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??2012-08-18
  • 0
    @Ryan You just can't multiply with a non-unit (and $35$ is also a non-unit) and assume you won't lose information. The analog of this to the usual situation would be taking an equation over $\mathbb{R}$, multiplying both sides by $0$ and noticing that the equation now has more solutions. Here it's a bit more subtle but it's really the same effect.2012-08-18
  • 0
    Thanks for the intuition -- I really needed that. Last thing I would like explicitly confirmed, if you please: is it correct that UNLIKE for regular simultaneous linear equations, solving simultaneous linear congruences requires that when selecting from the original system of eqns to solve for a variable (say $y$), the coefficient of $y$ needs to have the lowest possible gcd with the modulo base that one in working in ($42$ here).2012-08-18
  • 0
    @Ryan I think I understand what you're asking, and yes, you should do that.2012-08-18
  • 0
    Thanks. I will need more practice with such problems. Thanks again so much.2012-08-18