Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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