# Proof involving modulo multiplicative inverses

Assume that $m = x^{-1} \pmod y$. Is there an integer $n$ so that $n = y^{-1} \pmod x$? Prove or disprove.

Hello, this is question that I can't figure out. I am very confused on what its asking can anyone please explain exactly what this is asking me to do?

Thanks

-
What you cite gets my vote as confusing question. –  vonbrand Feb 13 '13 at 1:32

You have integers $x$ and $y$, and you’re told that there is an integer $m$ such that $mx\equiv 1\pmod y$. The question is whether this implies that there is some integer $n$ such that $ny\equiv 1\pmod x$. If there always is, you’re supposed to prove this; if there are integers $x,y$, and $m$ such that $mx\equiv 1\pmod y$, but no integer $n$ satisfies the congruence $ny\equiv 1\pmod x$, you’re supposed to produce such an example.

HINT: $mx\equiv 1\pmod y$ means that there is an integer $k$ such that $mx-1=ky$, and $ny\equiv 1\pmod x$ means that there is an integer $\ell$ such that $ny-1=\ell x$.

-

It's saying that $m x = 1 + k y$ for some integer $k$, and it's asking whether there is an integer $n$ so that $ny = 1 + j x$ for some integer $j$.

-

Hint $\rm\quad x\mid a\,\ (mod\ y)\iff \exists\, j,k\in\Bbb Z\!:\ jx + ky = a\iff y\mid a\,\ (mod\ x).\$ Hence, for $\rm\:a = 1\!:$

$$\rm x^{-1}\ exists\,\ (mod\ y)\iff x\mid 1\,\ (mod\ y)\iff y\mid 1\,\ (mod\ x)\iff y^{-1}\ exists\ \,(mod\ x)$$

Remark $\$ Further, recalling that $\rm\,\exists\, j,k\in\Bbb Z\!:\ jx + ky = a\iff (x,y)\mid a$

$$\rm x\mid a\,\ (mod\ y)\iff (x,y)\mid a \iff y\mid a\,\ (mod\ x).$$

which, for $\rm\, a =1,\,$ specializes to the well-known

$$\rm x^{-1}\ exists\,\ (mod\ y)\iff (x,y)\mid 1\iff y^{-1}\ exists\ \,(mod\ x)$$

These are special cases of relations between Bezout's identity and CRT (Chinese Remainder).

-
Divisibility $\rm\,(mod\ n)\,$ frequently proves conceptually handy, e.g. see this answer. –  Math Gems Feb 15 '13 at 16:49