Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
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$.

share|cite|improve this answer
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$.

share|cite|improve this answer
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.

share|cite|improve this answer
so succinct! i hope to look into the diophantine eqtn's. – IQ472 Jul 10 '12 at 2:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.