if $ax \equiv 1 \pmod{y}$ and $by \equiv 1 \pmod{x}$, then gcd$(x,y)=1$ I don't think someone has posted this question yet. One looks similar, but I wasn't sure. Sorry in advance if it is. 
I think I am making things up toward the end. I wanted to make a squeeze argument.
Suppose we are given:

$ax \equiv 1 \pmod{y}$ and $by \equiv 1 \pmod{x}$
where $a,b,x,y \in \mathbb{Z} $

Then it is true that, 
$$ \begin{align}
y &| 1-ax \\
x &| 1-by 
\end{align}$$
And since, $\gcd(y,x) | x,y$, it follows that the $\gcd(x,y) | 1-ax \ $ and $1-by$. So suppose the $\gcd(x,y) \geq 1$, then
$$ \begin{align}
1 \leq \gcd(x,y) \ | \ x \ | \ 1 -by 
\end{align}$$  
Similarly, 
$$ \begin{align}
1 \leq \gcd(x,y) \ | \ y \ | \ 1 -ax 
\end{align}$$ 
I wanted to say these last parts were less than or equal to one. But now I don't think that's true. 
 A: You only need one of the two statement to conclude that $(x,y) = 1$.
Lets consider the first statement alone. We have $ax = 1 + ny$.
Let $d$ be a common divisor of $x$ and $y$ i.e. $d \vert x$ and $d \vert y$.
Hence, $x = d m_x$ and $y= d m_y$.
This gives us that $ax - ny = a d m_x - n d m_y = d(a m_x - n m_y)$. Hence, $d$ divides $ax-ny$. But $ax - ny = 1$. Hence, $d$ divides $1$.
Hence, any common divisor of $x$ and $y$ has to divide $1$. Hence, $\gcd(x,y) = 1$.
A: The first condition already implies that $x$ and $y$ are relatively prime.
For suppose to the contrary that $d \gt 1$ divides $x$ and $y$. Then $d$ divides $ax$. Since $y$ divides $ax-1$, we find that $d$ divides $ax-(ax-1)$, that is, $d$ divides $1$, which is impossible.
The same argument shows that the second condition also, all by itself, implies that $\gcd(x,y)=1$.
A: Hint $\rm\ mod\ y\!:\ a\,x \equiv c\:\Rightarrow\: n\,y + a\,x = c\:\Rightarrow\:gcd(y,x)\:|\:c.\ $ Yours is the special case $\rm\:c = 1.$
Remark $\ $ This is a well-known criterion for solvability of a linear diophantine equation.
