# Mod inverse, GCD congruence

I'm having trouble understanding this question and the answer

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.

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

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})}$
• 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. – Carpetfizz Jan 21 '17 at 20:51
• $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). – Bill Dubuque Jan 21 '17 at 20:55
• 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.\ \$ – Bill Dubuque Jan 21 '17 at 20:57
• @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.\$ – Bill Dubuque Jan 21 '17 at 21:50