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

• Use \pmod{b} to produce the parenthetical (mod b) with proper spacing and typeface. Use \bmod b to produce the binary operator. Using \pmod also prevents breaks between the “mod” and the $b$. – Arturo Magidin Sep 1 '19 at 22:45
• Thanks @ArturoMagidin ! This helps a lot. I would waste a lot of time doing it the long way – john fowles Sep 1 '19 at 22:55

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.

• But how do we end up with $pa\equiv qa \pmod b$? Does this equivlence say that $qa$ is the remainder for $pa$? Or have I misread this line? – john fowles Sep 1 '19 at 22:59
• It says that $pa$ and $qa$ have the same remainder modulo $b$. – Berci Sep 1 '19 at 23:00
• This is what confuses me. Is it supposed to be read as, for e.g, $7\equiv 2 \pmod 5$? or is what is written in the proof something diferent, like, for e.g, $7\equiv 12 \pmod 5$? I'm not familiar with the latter expression – john fowles Sep 1 '19 at 23:08
• $a\equiv b\pmod m$ is formally defined as $m\,|\,b-a$, which means exactly that $a$ and $b$ give the same remainder modulo $m$. So, it's the more general one, and both of your congruences are correct. – Berci Sep 1 '19 at 23:14

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 rwhich leads to $$pa\equiv qa\pmod b$$

• How did you get the final line $pa \equiv qa \pmod b$? Maybe I'm reading it wrong, but I'm reading this as $qa$ being the remainder for $pa \pmod b$ – john fowles Sep 1 '19 at 22:57
• this is obtained from $$pa\equiv r\equiv qa\mod b$$ – Mostafa Ayaz Sep 2 '19 at 10:03

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.

• When I saw your (succinct) answer I lost interest in any pigeonhole/contradiction formulation. (+1). – CopyPasteIt Sep 2 '19 at 14:39

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.