Deriving integer solutions to quadratic equation without solving quadratic congruence

Question

I want to generate positive integer solutions of $x$ to the equation:

$x^2-x-aT=0$

where a is an integer $>$ 0 and T is a very large positive number.

I noticed that when plugging this into wolfram alpha is looks like it was formulating the equation in the form:

$x^2-x≡0 (mod T)$

And then solving this quadratic congruence to get the equations to generate all integer solutions to my equation.

I'm not keen on using this method to solve as in order for it to work it relies on first factorising T. If T is really large this will cause the solution to run in linear time (with respect to the number of digits of T) which doesn't scale to the size I want.

So what I am asking is:

Is there a way to generate integer solutions to my initial equation in logarithmic time without solving the quadratic congruence equation I showed above and without factorising T?

Answer 1

Erm... sorry, but this is just a quadratic equation, and the positive solution is $$x=\frac12+\sqrt{\frac14+T}.$$ I think it's fairly easy to check if this is an integer, even for very large $T$

Answer 2

$$ x^{\,2} - x = x\left( {x - 1} \right) = x^{\,\underline {\,2\,} } = 2\left( \matrix{ x \cr 2 \cr} \right) = T $$

So first of all $T$ must be even.
Then $$ \sqrt T < \approx x $$ and for large T you can check if $$ x = \left\lceil {\sqrt T } \right\rceil $$ works.

In any case you can use the Newton-Raphson method to find the root of $x^2-x-T=0$, and see if it is an integer.