2
$\begingroup$

I'm having trouble understanding this question and the answer

enter image description here

I know that if $GCD(z,n) = GCD(w,n) = 1$, that says that both $z^{-1}$ and $w^{-1}$ exist, but I'm unsure of the rest of the problem. I thought that if we could equate $z^{-1} = w^{-1}$ then we could say that multiplying both $x$ and $y$ by the same number wouldn't change their congruence, but I tried it with real numbers and of course that did not work.

EDIT: After coming back to this question, I'm afraid I don't understand the previously accepted answer. We didn't learn about modular arithmetic in terms of roots in our class, and I'm beginning to think there's a much simpler solution to this as these exams allot about 1 min / question. Any attempts to explain this in a different way would be much appreciated.

$\endgroup$
  • $\begingroup$ Yes, simply multiply the first congruence times the inverse of the second congruence. $\endgroup$ – Bill Dubuque Jan 21 '17 at 20:20
  • $\begingroup$ Thanks, do you mind providing an example? $\endgroup$ – Carpetfizz Jan 21 '17 at 20:21
3
$\begingroup$

To clarify let's rename $\,x,y,z,w\,$ to $\,A,a,B,b,\,$ so it becomes

If $\ \color{#0a0}{\gcd(b,n) = 1}\,$ then $\ {\rm mod}\,\ n\!:\ \begin{align}A\equiv a\\ B\equiv b\end{align}\ \Rightarrow\ \dfrac{A}B\equiv \dfrac{a}b,\ \ {\rm i.e.}\ \ AB^{-1}\equiv ab^{-1}$

Hint $\ A/B\,$ and $\,a/b\,$ are both roots of $\, b\,x\equiv a\ $ This has unique roots by $\color{#0a0}{\ b^{-1}\ {\rm exists}\pmod{\!n}}.\,$ Indeed if $\,x_1,\,x_2$ are roots then $\, \color{#c00}b\,x_1\equiv a\equiv \color{#c00}b\,x_2\,$ $\Rightarrow$ $\,x_1\equiv x_2\,$ by cancelling the $\color{#c00}b$'s $ $ (doable by multiplying through by $\,\color{#0a0}{b^{-1})}$

$\endgroup$
  • $\begingroup$ How are you equating $xz^{-1}$ and $yw^{-1}$ to $t$ ? I'm also not sure where $zt \equiv x$ comes from or how the language of roots applies to mod arithmetic. $\endgroup$ – Carpetfizz Jan 21 '17 at 20:51
  • $\begingroup$ $t$ is a variable. I would have used the customary notation $x$ but that would conflict with the notation in your problem (the choice of $x,y,z,w$ was poor here - that's why I used $a$'s and $b$'s instead). $\endgroup$ – Bill Dubuque Jan 21 '17 at 20:55
  • $\begingroup$ Ah yeah, I got that it's a placeholder but I still don't understand the concept of roots, and how both those quantities are equal to the same placeholder $\endgroup$ – Carpetfizz Jan 21 '17 at 20:55
  • $\begingroup$ We can study roots of polynomials mod $n$ too. Modular integers behave in many ways the same as ordinary integers. This will become clearer when you learn how to view the integers mod $n$ as a ring $\,\Bbb Z_{\large n} = \Bbb Z/n.\ \ $ $\endgroup$ – Bill Dubuque Jan 21 '17 at 20:57
  • 1
    $\begingroup$ @Carpetfizz $\,x_i\,$ is a root of $\,bx\equiv a\,$ means $\,b x_i\equiv a.\,$ Note $\,B\equiv b\,\Rightarrow\, \gcd(B,n) = \gcd(b,n)\,$ so $\,B^{-1}\,$ exists $\iff b^{-1}\,$ exists; further $\,B^{-1}\equiv b^{-1}\,$ by the special case $\,A\equiv 1\equiv a\,$ in the proof. The notation $\,c/d\,$ means $\,cd^{-1}\ $ (that this is *well-defined* is the point of the above proof, i.e. it doesn't depend on the choice of rep for the num/denominator). Fraction arithmetic works mod $n$ as long as you restrict to denominators that are invertible, i.e. coprime to $n.\ $ $\endgroup$ – Bill Dubuque Jan 21 '17 at 21:50

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.