-1
$\begingroup$

If we take ceil and floor of $\sqrt{x(x+1)}$ (when it exists) we get $x$ and $x+1$ respectively. Is there an analog of this assuming roots exist in modular arithmetic (at least modulo primes)?

Assuming $\sqrt{x(x+1)}=b$, I know we can solve by solving the quadratic equation $x^2+x-b^2=0$. I just want to know if there is a way to solve without going through the quadratic equation.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The motivation for a ceil/floor function is unclear to me. In any case there isn't always a solution to x^2=b mod p. For example x^2=2 mod 3 has no solutions. $\endgroup$
    – sendit
    Commented Nov 19 at 18:53
  • $\begingroup$ @sendit clarified. $\endgroup$
    – Turbo
    Commented Nov 19 at 19:00
  • $\begingroup$ The first paragraph is not in harmony with the second paragraph. Specifically, the fact that the real number $\sqrt{x(x+1)}$ lies between $x$ and $x+1$ (for $x$ nonnegative) does not seem to help in solving quadratic equations of the form $x^2+x=b^2$ in real numbers. At any rate, assuming GRH (which is okay for pratical purposes), there is a fast algorithm for taking square-roots modulo $p$, hence also for solving quadratic equations modulo $p$. $\endgroup$
    – GH from MO
    Commented Nov 19 at 23:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .