For $a,b$ coprime, there exists positive integers $x,y$ such that $ax-by=1$

The problem statement is: for $a,b$ coprime, prove that there exists positive integers $x,y$ such that $ax-by=1$. The question is form Arthur Egnels' problem solving text, and from the chapter on the pigeonhole principle.

My question: His proof begins by generating a list $a,\ldots,a(b-1)$, where he then points out that each element in this list(which proceeds sequentially) doesn't have remainder $0\pmod{b}$. He then shows that we arrive at a contradiction if we assume that we also don't get remainder $1$ in this list $\bmod b$. To show the contradiction in this last statement, he first states that we would have positive integers $p,q $ where $ 0<p<q<b$ so that $pa\equiv qa \pmod{b}$. He then goes on to point out that since we $a$ and $b$ are coprime, we then have that $b| q-p$. I understand the last part here, but don't see why we get $pa\equiv qa \pmod{b}$.

Thanks in advance

Solution 1:

There are $b-1$ elements written up, with $b-1$ possible remainders (omitting $0$).
If any further remainder is omitted, two of them must be equal, by pigeon-hole.

Solution 2:

If $1$ is not among the remainders, we must have one remainder repeated at least twice since the total number of remainders $\bmod b$ is $b$. i.e.$$\exists 0\le r<b\\pa\equiv r\pmod b\\qa\equiv r\pmod b\\p\ne q$$which leads to $$pa\equiv qa\pmod b$$

Solution 3:

It is $\,(3\Rightarrow 4)\,$ below (with $\,\rm m = b)$.

Theorem $\, $ The following are equivalent for integers $\rm\:a, m.$

$(1)\rm\ \ \ gcd(a,m) = 1$
$(2)\rm\ \ \ a\:$ is invertible $\rm\ \ \ \ \: (mod\ m)$
$(3)\rm\ \ \ x\,\mapsto\, ax\:$ is $\:1$-$1\:$ $\rm\,(mod\ m),\ $ i.e. $\rm\,ax\equiv ay\Rightarrow\,x\equiv y,\ $ i.e. $\rm\ a\,$ is cancellable
$(4)\rm\ \ \ x\,\mapsto\, ax\:$ is onto $\rm\,(mod\ m),\ $ i.e. $\rm \ ax\equiv b\,$ is solvable for all $\rm\,b.$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(a,m)\! =\! 1\Rightarrow ja\!+\!km =\! 1\,$ for $\rm\,j,k\in\Bbb Z\,$ $\rm\Rightarrow ja\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm ax \equiv ay\,\Rightarrow\,x\equiv y\,$ by scaling by $\rm\,a^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to ax\,$ onto $\,\Rightarrow\rm \exists\,j\!:\, aj\equiv 1\,$ $\rm\Rightarrow\exists\,j,k\!:\ aj\!+\!mk = 1$ $\,\Rightarrow\,\rm\gcd(a,m)\!=\!1$

See here for a conceptual proof of said Bezout identity for the gcd.

Solution 4:

First note that the statement "each element in this list(which proceeds sequentially) has remainder $0$ mod $b$" is not correct. In fact none of them have remainder $0$ mod $b$.

This is an important point because it means that there are only $b-1$ possibilities for these remainders mod $b$.

Now there are precisely $b-1$ of these remainders and so either two are the same or every possible remainder (including $1$) must occur. If two are the same one has $pa\equiv qa$ and the rest of the argument you understand.