# 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.

-
Just a passing comment: more generally, let $a,b$ be elements of a commutative ring $R$ such that $ax \equiv 1 \pmod{y}$. Then $x$ is a unit in $R/(y)$, so $(x) + (y)$ is the unit ideal of $R/(y)$ and thus $(x)+(y) = R$. In other words, in general either one of the two conditions implies that $x$ and $y$ are comaximal. – Pete L. Clark Jul 10 '12 at 2:28
Above, I should have said "let $a,x,y$ be elements...". – Pete L. Clark Jul 10 '12 at 9:41

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$.

-
thanks. i was just trying not to use that fact, I was curious if there was another way... – IQ472 Jul 10 '12 at 2:22
thank you for being a little more explicit. it really helps :) – IQ472 Jul 10 '12 at 2:29

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$.

-
thanks a lot! this was really helpful! – IQ472 Jul 10 '12 at 2:27

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.

-
so succinct! i hope to look into the diophantine eqtn's. – IQ472 Jul 10 '12 at 2:45