2
$\begingroup$

Let $a$ and $b$ be two positive integers such that gcd$(a,b)=1$. Prove that there exists $(x,y)\in\mathbb{Z}\times \mathbb{Z}$ satisfying

(1) $ax-by=1$

(2) $0<x<b$ and $0<y<a$.

I know (1) is by the fact that gcd$(a,b)=1$ but I don't know how to prove (2). Any hint?

$\endgroup$
3
$\begingroup$

The condition (2) cannot be satisfied if $a=1$ or $b=1$, so assume $a>1$ and $b>1$.

Choose $x_0$, $y_0\in\Bbb Z$ with $ax_0-by_0=1$. Then $x_0\not\equiv0\pmod{b}$ and so there is $t\in\Bbb Z$ with $x_1=x_0+tb$ satisfying $0<x_1<b$. Then $ax_1-by_1=1$ with $y_1=y_0-ta$. Then $$y_1=\frac{ax_0-1}{b}$$ so $$\frac{a-1}b\le y_1<\frac{ab-1}{b}$$ from which $0<y_1<a$.

$\endgroup$
2
$\begingroup$

First of all, if $a$ or $b$ equals $1$, then the claim is false, so suppose they are both greater than $1$.

Suppose $(x_0,y_0)$ is one solution. Then we also have that $(x_0+kb,y_0+ka)$ is a solution for any integer $k$. (Do you see why?)

Choose the value of $k$ that makes $x=x_0+kb$ as small as possible while still positive; then $x<b$, or we could have chosen a smaller value of $k$. Then we have:

$$by=ax-1<ab-1$$

Divide by $b$ and see what you get. This establishes why we have $y<a$.

To see why $y>0$, all we need is that $ax>1$, which follows from $a>1$ and $x>0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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