On $a^{2t}+b^{2t}=1\bmod n$ For every $\epsilon\in(0,1)$ is there an $n_0\in\Bbb N$ such that at every $n\in\Bbb N_{>n_{0}}$ we can have coprime solutions $a,b$ (over $\Bbb Z$) such that $n^{\frac1{2t}+\epsilon}<a,b<2n^{\frac1{2t}+\epsilon}$ holds for $ a^{2t}+b^{2t}=1\bmod n$ provided $1\le t\le\frac{\log n}{\log\log n}$ holds and is there an effective efficient algorithm under reasonable hypothesis?
 A: If $n$ is prime this is quite likely to be true but is beyond reach of current techniques (for $t>1$) as we can only estimate the number of points with coordinates in an interval of size $\sqrt n$.
If $n$ has many prime factors, I think this is unlikely. As soon as $n$ has $r$, say, prime factors of roughly equal size $m = n^{1/(2t)+\epsilon}$, the interval given has only one representative of each residue class modulo such a prime. If $p$ is one of those primes, the number of pairs of residue classes $\pmod p$ satisfying $a^{2t} + b^{2t} \equiv 1 \pmod p$ is roughly $p$ (Weil bound), so the chances that a random pair $a,b$ with $m < a,b < 2m$ satisfies the congruence modulo $p$ is about $1/m$ but you have $r$ conditions so the probability is $1/m^r$ (assuming independence) but you only have $m^2$ pairs, so unlikely if $r>2$. How big is $r$? We have $m^r$ about $n$ so $r(1/(2t)+\epsilon)$ is about $1$, so $r>2$ as soon as $\epsilon < 1/2 - 1/(2t)$. I guess we need $t>1$ for this to work.
