Why does the following theorem both provide a neccesary and sufficient condition for a $2 \times 2$ linear system of congruences to have a unique solution ?

I see that $\gcd((ad-bc),m) = 1$ is a neccesary condition for the solutions to exists.

However for this condition to imply that there exists unique solutions $x \equiv x_0 (\mod m)$ and $y \equiv y_0 (\mod m)$ to the original system, we must work backwards ? But how is this possible ?

In the proof we actually assume the solutions exist and then find the neccesary condition, namely $\gcd((ad-bc),m) = 1$. However, the other way is unclear to me?

enter image description here enter image description here

  • 1
    $\begingroup$ This is very badly explained in the textbook -- if a student wrote this in an exam, I'd reach for my red pen. $\endgroup$ – David Loeffler May 22 '14 at 16:37
  • $\begingroup$ Would you explain ? Am I right that the theorem in Koshy's textbook on Elementary Number Theory only prove one way of the bi-implication ? Is the other way "obvious" so it is left out ? If you understand the proof, but think it is badly explained, would you explain it to me shortly ? (I would be grateful). Thank you. $\endgroup$ – user141901 May 22 '14 at 19:00
  • 1
    $\begingroup$ The proof shows only that if $\,(\Delta,m) = 1\,$ and if a solution exists, then the solution is unique. It is not a complete proof of the theorem. $\endgroup$ – Bill Dubuque May 23 '14 at 0:48
  • $\begingroup$ Thanks just what I neeeded to hear ! I thought I didn't see the "obvious" in front of me. Nice to hear I was right in my assumption, that is the proof only show one way of the bi-implication. $\endgroup$ – user141901 May 23 '14 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy