# Number of solutions to $x_1x_2=x_3x_4\bmod n$

In https://www.math.ksu.edu/~cochrane/research/xyuvmodp.pdf it is shown $x_1x_2=x_3x_4\bmod p$ where $p$ is a prime has $\frac{|\mathcal B|}p+O(\sqrt{|\mathcal B|}\log^2p)$ solutions $(x_1,x_2,x_3,x_4)\in\mathcal B$ where $\mathcal B=\mathcal I_1\times \mathcal I_2\times \mathcal I_3\times \mathcal I_4$ with $\mathcal I_i=[a_i,b_i]\cap\Bbb N$ for some $a_i<b_i$?

Is it possible to replace prime $p$ with composite $n$ in here?

I also want $gcd(x_1,x_3)=gcd(x_2,x_4)=1$.

Actually I am also curious why this naive argument below will not work?

I show this for case when $\mathcal I_1=\mathcal I_3=\mathcal U$ and $\mathcal I_2=\mathcal I_4=\mathcal V$ for any composite $n$. It should work for any intervals since I use only size of intervals for estimation.

I want to show $x_1x_2=x_3x_4 \bmod n$ has a solution with $x_1,x_3\approx n^r$ and $x_2,x_4\approx n^{1-r+\epsilon}$ where $r\in(0,1)$ is fixed and $\epsilon>0$ is small and fixed and for every $n\in\Bbb N$ large enough.

Fix $a\in\Bbb Z_n^\times$ and $r\in(0,1)$ and consider $uv=a\bmod n$ where $n$ is composite. Vary $u\in\mathcal U$ and $v\in\mathcal V$ where $\mathcal U=[n^r,2n^r]$ and $\mathcal V=[n^{1-r}\log n,2n^{1-r}\log n]$ such that $gcd(u,n)=gcd(v,n)=1$. Since $|\mathcal U\times \mathcal V|=|\mathcal U|\times|\mathcal V|=n\log n$ is approximately the same count as number of integers which are coprime to $n$ in $\mathcal U\times \mathcal V$ and number of residue classes are only at most $(n-1)$ there is a residue class $a\in\Bbb Z_n$ and a two pairs $(u_1,v_1),(u_2,v_2)\in\mathcal X\times\mathcal Y$ such that $$u_1v_1=u_2v_2\bmod n$$ holds and there should at least be $\log n$ such solutions for $$x_1x_2=x_3x_4=a\bmod n$$ where $a$ is varied over all residue classes in $\Bbb Z_n^\times$.

I think can also take $gcd(x_1,x_3)=gcd(x_2,x_4)=gcd(x_1x_2x_3x_4,n)=1$ with this argument.

I think I can use the PNT to look for only primes in $\mathcal U$ and $\mathcal V$ and still make the argument work if $\mathcal V=[n^{1-r}\log n,2n^{1-r}\log n]$ is replaced by $\mathcal V=[n^{1-r}\log^3 n,2n^{1-r}\log^3 n]$ and get condition $gcd(x_1,x_3)=gcd(x_2,x_4)=1$. By avoiding the at most $\log n$ primes that divide $n$ I can also get $gcd(x_1x_2x_3x_4,n)=1$.

From Prime Number Theorem the number of primes in $\mathcal U=[n^r,2n^r]$ is $\frac{(1-\epsilon)n^r}{r\log n}$ and number of primes in $\mathcal V=[n^{1-r}(\log n)^3,2n^{1-r}(\log n)^3]$ is $\frac{(1-\epsilon)n^{1-r}(\log n)^2}{r^3}$ and so total prime tuples in $\mathcal U\times \mathcal U\times \mathcal V\times \mathcal V$ is $\frac{(1-\epsilon)^4n^2(\log n)^2}{r^8}$ which if $\frac{(1-\epsilon)^4n(\log n)^2}{r^8}>1$ provides more tuples than number of residues (using half of the primes in $\mathcal U$ for $x_1$ and half for $x_3$ and likewise using half of the primes in $\mathcal V$ for $x_2$ and half for $x_4$ will guarantee coprimeness among prime solutions and to encode for a loss in fraction of about $\frac1{16}$ we can use $\frac{(1-\epsilon)^4n(\log n)^2}{16r^8}>1$ as criteria).

• see someone is downvoting and someone emails me now and then from moderator. Who is downvoting? how can I make problem better? If someone recommends instead of downvoting I can incorporate. – T.... May 22 '16 at 11:57
• They probably saw only the title and thought you were asking about the number of solutions not restricted to interval $-$ which would indeed be a rather elementary problem for this forum. – Noam D. Elkies May 22 '16 at 20:44
• @NoamD.Elkies thank you and so is my elementary pigeonhole argument flawed for case $I_1=I_3$ and $I_2=I_4$ (at least rougly without including zero divisor)? – T.... May 22 '16 at 20:45
• I didn't read carefully through your argument (nor the paper you cite), but even if it works you get only a result for the special case $I_1=I_3$, $I_2=I_4$ of what that paper does for prime $n$. – Noam D. Elkies May 22 '16 at 21:08
• @NoamD.Elkies For my purposes $I_1=I_3$ and $I_2=I_4$ is sufficient provided $gcd(x_1,x_3)=gcd(x_2,x_4)=gcd(x_1x_2x_3x_4,n)=1$. I think I can achieve this with my arguments. – T.... May 22 '16 at 22:01