# Negative Dirichlet Pigeonhole Principle

From Dirichlet Pigeonhole Principle if $$p$$ is a prime and if $$a,b\in\mathbb Z$$ are in $$(0,p/2)$$ then there is a $$t\in(0,p)\cap\mathbb Z$$ such that $$\|(x,y)\|_\infty<\lceil\sqrt p\rceil$$ holds where $$t(a,b)\equiv(x,y)\bmod p$$.

1. Is there no distinct coprime $$a,b$$ in $$(0,\lceil\sqrt p\rceil)$$ such that there is $$t\in(0,p)\cap\mathbb Z$$ with $$\|(x,y)\|_\infty<\|(a,b)\|_\infty$$?

From Dirichlet Pigeonhole Principle if $$p$$ is a prime and if $$a,b,c\in\mathbb Z$$ are in $$(0,p/2)$$ then there is a $$t\in(0,p)\cap\mathbb Z$$ such that $$\|(x,y,z)\|_\infty<\lceil p^{2/3}\rceil$$ holds where $$t(a,b,c)\equiv(x,y,z)\bmod p$$.

1. Is there no distinct pairwise coprime $$a,b,c$$ in $$(0,\lceil p^{1/3}\rceil)$$ such that there is $$t\in(0,p)\cap\mathbb Z$$ with $$\|(x,y,z)\|_\infty<\|(a,b,c)\|_\infty$$? Is it possible to increase size of $$a,b,c$$ to a larger value than $$\lceil p^{1/3}\rceil$$?
• Do you mean for $t$ in your question to also lie in $(0,p)$? If so, then $(a,b)=(1,1)$ trivially implies the answer is "no" – Wojowu Dec 24 '18 at 13:41
• Let $(a,b)=(2,2)$ then. For $t=(p+1)/2$, $(x,y)=(1,1)$. – Wojowu Dec 24 '18 at 13:45
• $(a,b)=(2,4),t=(p+1)/2,(x,y)=(1,2)$ – Wojowu Dec 24 '18 at 13:47
• @Wojowu coprime $a,b$. – Brout Dec 24 '18 at 13:52

No. Observe that $$a/b=x/y$$, from which it follows that $$ay=xb$$. Since $$a,b,x,y$$ are all in $$(0,\sqrt{p})$$, it follows that the equality $$ay=xb$$ holds not merely mod $$p$$, but in $$\mathbb{Z}$$. Since $$a,b$$ are coprime, it follows that $$a\mid x$$ and $$b\mid y$$. Hence, $$\lvert x\rvert\geq \lvert a\rvert$$ and $$\lvert y\rvert\geq \lvert b\rvert$$.
• If $p$ is not a prime does something like this hold at least when $p$ is square free odd and has only $O(1)$ prime factors? – Brout Dec 25 '18 at 8:54