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