1
$\begingroup$

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.

  • 0
    Above, I should have said "let $a,x,y$ be elements...".2012-07-10

3 Answers 3

5

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

  • 0
    thank you for being a little more explicit. it really helps :)2012-07-10
4

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

  • 0
    thanks a lot! this was really helpful!2012-07-10
1

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.

  • 0
    so succinct! i hope to look into the diophantine eqtn's.2012-07-10