1
$\begingroup$

Let $p$ and $q$ be large primes in $[T,2T]$ where $T$ is a parameter.

  1. Can we have same integer pair $a,b$ satisfying $ab\equiv c'\bmod p$ and $ab\equiv c''\bmod q$ such that both $|c'|$ and $|c''|$ are $O(\operatorname{polylog}(T))$ and $|a|,|b|$ of size $O(T^{3/4}\operatorname{polylog}(T))$?

  2. If $3/4$ is impossible what is the best rational in exponent we can get?

  3. Given $p,q$ how many generically positioned small near-reciprocal pairs are possible?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is one of the $p$ in 1 supposed to be $q$? $\endgroup$
    – Wojowu
    Commented Apr 23, 2022 at 6:48
  • $\begingroup$ Why not just try $c^\prime = 3$ and $c^{\prime \prime} = 5$ then sample $a,b$'s in some range? I bet most of the time both $ab - 3$ and $ab - 5$ have a large prime divisor. $\endgroup$
    – Stanley Yao Xiao
    Commented Apr 23, 2022 at 11:58
  • $\begingroup$ That is why this problem may not be easy to answer. $\endgroup$
    – Turbo
    Commented Apr 23, 2022 at 12:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .