Let ${p}$ be a prime. $a,b,c\in\mathbb Z,\gcd(a,p)=\gcd(b,p)=\gcd(c,p)=1.$ Prove that: $\exists x_1,x_2,x_3,x_4\in\mathbb Z,| x_1|,|x_2|,|x_3|,|x_4|<\sqrt p,$ satisfying $$ax_1x_2+bx_3x_4\equiv c\pmod p.$$Proposed by Wang Guangting
Problem
Source: 2023 CWMO P4
Tags: modular arithmetic, number theory
20.08.2023 08:48
Take everything here $\mod p$. By scaling, WLOG let $a=1$. Firstly, by Thue's Lemma, there exists $x_3$ with $0 < x_3 < \sqrt{p}$ such that $0 < bx_3 < \sqrt{p}$. Let $d=bx_3$. Case 1: $\frac{\sqrt{p}}{2} < d < \sqrt{p}$ Then set $x_1=1$. Note that by swapping the signs of $x_2,x_4$, we may WLOG assume that $0 < c < \frac{p}{2}$. Consider the numbers \[d,2d,\dots (\lfloor \sqrt{p} \rfloor + 1)d\]Since $(\lfloor \sqrt{p} \rfloor + 1)d > \sqrt{p}d > \frac{p}2 > c$, there must exist $i$ with $0 \le i <\sqrt{p}$ such that $id \le c < (i+1)d$, and thus $c-id < d < \sqrt{p}$. Hence, we may set $x_4 = i, x_2=c-id$. Case 2: $0 < d < \frac{\sqrt{p}}{2}$ Again, by flipping signs we may assume that $0 < c < \frac{p}4$ or $\frac{p}2 < c < \frac{3p}4$. First, we can find a $x \in (\sqrt{p}-d,\sqrt{p})$ such that $\gcd(d,x)=1$ (say by picking $x \equiv 1 \mod d$). If $0 < c < \frac{p}4$, we consider the numbers \[c+d, c+2d, \dots c+xd \]Clearly, they are all smaller than $p$. Furthermore, at least one of them will be divisible by $x$. Let it be $c+id$. Then I claim $x_4=-i, x_1=x,x_2 = \frac{c+id}{x}$ works. Indeed, all we need to show is that $x_2 < \sqrt{p}$. We see that \[x_2 \le \frac{c+xd}{x} = \frac{c}{x} + d < \frac{p/4}{\sqrt{p}-d} + \frac{\sqrt{p}}{2} < \frac{p/4}{\sqrt{p}/2}+\frac{\sqrt{p}}2 = \sqrt{p}\]as desired. If $\frac{p}2 < c < \frac{3p}4$, then consider the numbers \[c-(\lfloor \sqrt{p} \rfloor +1-x)d, \dots c-\lfloor \sqrt{p} \rfloor d\]Clearly, all of these are positive, and furthermore one of them is divisible by $x$. Again, let it be $c-id$. I claim $x_1=x, x_2=\frac{c-id}{x}, x_4=i$ works. Indeed, \[x_2 < \frac{c-(\lfloor \sqrt{p} \rfloor +1-x)d}{x} < \frac{c-(\sqrt{p}-x)d}{x} = \frac{c-\sqrt{p}d}{x} + d < \frac{3p/4 - \sqrt{p}d}{\sqrt{p}-d} + d = \frac{3p/4 - d^2}{\sqrt{p}-d} = \sqrt{p} - \frac{p/4 -d\sqrt{p} + d^2}{\sqrt{p}-d}= \sqrt{p} - \frac{p/4 - d(\sqrt{p}-d)}{\sqrt{p}-d} < \sqrt{p}\]where the last step follows from $\frac{p}{4} > d(\sqrt{p}-d)$ by AM-GM. Hence, we are done.
04.10.2023 09:19
We use a well known NT Lemma to prove this. Lemma(Thue) : Let ${p\ge 3}$ be a prime, ${a}\in\mathbb N_+$ and $\gcd (a,p)=1.$ Then $\exists x,y\in\mathbb Z,xy\neq 0,|x|,|y|<\sqrt p$ satisfying $a\equiv xy^{-1}\pmod p.$ Proof : consider all numbers that can be written as $x-ay$ where $x,y\in\mathbb Z,xy\neq 0,|x|,|y|<\sqrt p.$ There are $([\sqrt p]+1)^2-1>p-1$ numbers in total. If $\exists p\mid x-ay,$ we are done. If not, there must exists $(x_1,y_1)\neq (x_2,y_2)$ such that $x_1-ay_1\equiv x_2-ay_2\pmod p.$ Therefore $p\mid x_1-x_2-a(y_1-y_2).$ Noticing that $|x_1-x_2|,|y_1-y_2|<\sqrt p,$ we are done.$\blacksquare$ Solution : By Lemma, $\exists x_1,x_3$ such that $x_1x_3^{-1}\equiv a^{-1}b([\sqrt p]+1)x\pmod p,$ then $LHS\equiv bx_3(([\sqrt p]+1)x_2+x_4)\pmod p.$ We consider a function $f:\left(\{0,1,\cdots ,[\sqrt p]\},\{0,1,\cdots ,[\sqrt p]\}\right)\to \{0,1,\cdots ,[\sqrt p]^2+2[\sqrt p]\},$ let $f(a,b)=([\sqrt p]+1)a+b.$ It is obvious that ${f}$ is both injective and surjective. From $[\sqrt p]^2+2[\sqrt p]=([\sqrt p]+1)^2-1>p-1\Rightarrow [\sqrt p]^2+2[\sqrt p]\ge p.$ Therefore $\exists x_2,x_4\in\mathbb Z,|x_2|,|x_4|<\sqrt p,[\sqrt p]+1)x_2+x_4\equiv c(bx_3)^{-1}\pmod p,$ so $LHS\equiv RHS\pmod p,$ we are done.$\blacksquare$