I am trying to find a way to describe all integer values of $x$ for which the following holds true:

$\sqrt[2]{(1/2) * x * (x - 1) + (1/4)} + (1/2)\in \mathbb{Z}$

Noting that this can be equivalently stated as:

$2*\sqrt[2]{(1/2) * x * (x - 1) + (1/4)} \equiv 1 (mod 2)$

I am aware of the fact that, via Hensel's Lemma, if I can make the left-hand side a polynomial with integer coefficients, then the solutions can easily be found. Thus, I'm trying to manipulate this congruence to make it a polynomial congruent to $0$ modulo a prime. I believed that perhaps the following was equivalent to the above expression:

$4*((1/2)*x*(x-1)+(1/4)) \equiv 1 (mod 4)$

(I.e., just squaring both sides of the congruence as well as the modulo.)

Which could then trivially be manipulated to show that:

$2*x*(x-1) \equiv 0 (mod 4)$

However, it is easy to see that this is no longer equivalent by a simple counter-example (e.g., the first statement fails for $x = 121$, whereas the second statement is true). Squaring both sides of a congruence (at least in this way) doesn't seem to make any sense.

Is there a technique I can use to remove the radical from this congruence, or am I going about this the wrong way? I would prefer hints or general techniques, rather than an explicit solution to this particular problem.


It seems the following.

Usually congruences are used for integer numbers, not for the reals. So solving your problem we should find an integer $y$ such that $x(x-1)/2+1/4=(y-1/2)^2$, that is $2(2y-1)^2-(2x-1)^2=1$. This is a partial case of minus Pell’s equation.

  • $\begingroup$ This is great. I'm not totally convinced working with modulo arithmetic couldn't work, but reducing this problem to Pell's equation is honestly a more elegant solution anyway. Thanks! $\endgroup$ – CmdrMoozy Dec 11 '13 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.