Linear Diophantine equation $ax-by=1$

Question

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?

Answer 1

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

Answer 2

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