I must confess I'm finding it pretty hard to get my head round these equations, much less solve them. So any help would be enormously appreciated. I'd appreciate if you'd show the logic of how to solve these, and keep it simple without explicitly mentioning the Extended Euclidean what have you, and all this other stuff. (I've seen it mentioned in other answers, but it's impenetrable to me). I'm only interested in the step-by-step process, and how it works, rather than just quoting formulaic methods. So please keep it simple and jargon-free. Thank you. Equations are:

$$ \begin{cases} z_1 (8z_2 + 2) = 3 \mod 11\\ z_2 (4z_1 + 11) = 5 \mod 13 \end{cases} $$ I'm trying to solve for $z_1$ and $z_2$ modulo whatever.

  • $\begingroup$ Can we use the fact that the integers modulo $11, 13$ form fields, or are you wanting these equations modulo any numbers, not necc. prime? Please state the most general form of the equation you're wishing to solve. $\endgroup$ – Shine On You Crazy Diamond Feb 27 '18 at 0:12
  • $\begingroup$ It certainly looks to me at first glance that you’d be looking for a congruence modulo $143=11\cdot13$. I find the setup puzzling, though. $\endgroup$ – Lubin Feb 27 '18 at 2:59
  • $\begingroup$ @EnjoysMath: Not sure what you mean by fields, but am not bothered modulo what numbers you solve the equations for, although as Lubin said, I had an inkling it might be modulo 143. $\endgroup$ – Dolphin Feb 27 '18 at 10:50

So you will have $10$ answer pairs for the first equation.

Each of these is obtained by getting the inverse of some chosen value of $z_1$ and then solving for $(8z_2 + 2) \equiv 3z_1^{-1} \bmod 11$ which calculates out to $z_2\equiv 7(3z_1^{-1}-2) \bmod 11$ since $8^{-1}\equiv 7 \bmod 11$.

You know in advance that $z_1\equiv 0 \bmod 11$ is not going to give a solution. Note that $z_2\equiv 0$ can be a solution though; in fact $(z_1,z_2)\equiv (7,0)\bmod 11$ is a solution for the first equation.

So for example with $z_1\equiv 6$, we know $z_1^{-1}\equiv 2$ so $z_2 \equiv 7(3\cdot 2 -2) \equiv 28\equiv 6 \bmod 11$.

Similarly you will have $12$ answer pairs for the second equation. Here of course $z_2\equiv 0 \bmod 13$ cannot be a solution, but this time $z_1\equiv 0$ is feasible and $(z_1,z_2)\equiv (0,4)\bmod 13$ satisfies the requirement.

Combining every solution to the first equation with every solution to the second through the Chinese Remainder Theorem, you will have $120$ answer pairs $\bmod 143$.

An example: combining $(6,6)\bmod 11$ with $(0,4)\bmod 13$ gives $(z_1,z_2)\equiv(39,17)\bmod 143$ as one of the answer pairs.


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.