2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ – Arturo Magidin Sep 1 '19 at 22:45
  • $\begingroup$ Thanks @ArturoMagidin ! This helps a lot. I would waste a lot of time doing it the long way $\endgroup$ – john fowles Sep 1 '19 at 22:55
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – john fowles Sep 1 '19 at 22:59
  • $\begingroup$ It says that $pa$ and $qa$ have the same remainder modulo $b$. $\endgroup$ – Berci Sep 1 '19 at 23:00
  • $\begingroup$ 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 $\endgroup$ – john fowles Sep 1 '19 at 23:08
  • 2
    $\begingroup$ $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. $\endgroup$ – Berci Sep 1 '19 at 23:14
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$ – john fowles Sep 1 '19 at 22:57
  • $\begingroup$ this is obtained from $$pa\equiv r\equiv qa\mod b$$ $\endgroup$ – Mostafa Ayaz Sep 2 '19 at 10:03
3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.