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
Best Answer
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.