Completing the square modulo $p$

Question

(Admittedly, this question is inspired by one of the questions I was thinking for my Algebraic Number Theory class but I don't think the question that I am about to ask needs much knowledge of Algebraic Number Theory.)

Suppose $d$ is an integer that is congruent to $1$ mod $4$, so that $\frac{d-1}{4}$ is an integer. Let $p$ be an odd prime. I was thinking about when will this equation $X^2-X-\frac{d-1}{4}$ have repeated roots modulo $p$?

I know that we can rewrite this equation as $(X-\frac{1}{2})^2-\frac{d}{4}$ and so does it imply that $\frac{d}{4}\equiv0$ mod $p$? I cannot see why it would imply this and besides, couldn't we 'complete the square in a different way' because $X^2-X-\frac{d-1}{4}\equiv X^2-(1+mp)X-\frac{d-1}{4}$ for any integer $m$ and then we use the latter expression to complete the square and we could potentially get a different answer?

Thank you so much in advance!

Answer 1

Nice question, there are a few points to be made, so let me proceed in order. Let $f(x) = x^2 - x - (d-1)/4 = (x-1/2)^2 - d/4$. I will always tacitly use the fact that $p$ is odd.

Sometimes there are no roots

Suppose there is a solution to $f(x)\equiv 0$ modulo $p$. Then $(2x-1)^2 \equiv d$. But this is not always possible to solve: it depends if $d$ is a quadratic residue or not, modulo $p$.

If $d$ is not a quadratic residue modulo $p$, then $f(x)$ has no roots modulo $p$.

There are roots if and only if $\sqrt d$ exists modulo $p$

Viceversa, suppose that $d$ is a quadratic residue modulo $p$. This means that there is some residue $s$ modulo $p$ such that $(-\pm s)^2 \equiv d$ modulo $p$. Moreover, each quadratic residue has at most two squareroots modulo $p$, namely $+s$ and $-s$ (*).

But then solving $f(x)\equiv 0$ is equivalent to solve the congruence $2x-1 \equiv \pm s$. We may use the notation $''s = \sqrt d''$ because indeed $s$ is a choice of squareroot residue modulo $d$. With this notation we get:

If $d$ is a quadratic residue modulo $p$, then the congruence $f(x)\equiv 0$ has the following solutions: $$ x \equiv \frac 1 2 \pm \frac {\sqrt d} 2 .$$

There are roots if and only if $\sqrt \Delta$ exists modulo $p$

This is part of a bigger truth, and all comes down to the discriminant $\Delta = b^2 - 4ac$. In this case the discriminant of $f(x)$ is precisely $$\Delta = 1+(d-1) = d.$$

It comes with no surprise then that *the solutions of the quadratic congruence $f(x)\equiv 0$ are $$x\equiv \frac{-b \pm \sqrt \Delta}{2a} = \frac {1\pm \sqrt d}{2},$$ provided that $\Delta$ is a quadratic residue modulo $p$.

Factorization approach

One simple alternative way to approach the problem is by trying to factorize after completing the square. We have seen that, if $d$ is not a quadratic residue, then there are no solutions. If instead $d$ possesses a squareroot $s$ modulo $p$, which we will just denote $\sqrt d$, then the polynomial $f(x)$ can be seen as a difference of squares, and so it factors:

$$f(x) = \left (x-\frac 1 2 \right)^2 - \left(\frac {\sqrt d } 2\right)^2 = \left(x-\frac 1 2 +\frac {\sqrt d } 2\right)\left(x-\frac 1 2 -\frac {\sqrt d } 2\right).$$

Now, remember that products modulo $p$ have the property $$AB\equiv 0\quad \Rightarrow \quad A\equiv 0 \quad or \quad B\equiv 0.$$ This is true because $p$ is prime!

Then we can solve the linear factors separately, and get the "two" solutions.

Repeated roots

Now that we found the roots, we see that they are equal if and only if $+\sqrt d \equiv -\sqrt d$. This simply means $\sqrt d\equiv 0$. This means $d=0$.

Note that $d\equiv 0$ automatically implies that $\sqrt d$ exists modulo $p$ (and is equal to zero :)

This is again part of a bigger truth:

The quadratic congruence has a repeated root if and only if $\Delta \equiv 0$.

Why there are precisely "two" squareroots

Suppose that $d$ is a quadratic residue. Then there is some $s$ such that $s^2=d$. How to prove that the only solutions to $x^2\equiv d$ has the only solutions $x\equiv \pm s$?

Simply, as before: we need $x^2-d\equiv 0$. Therefore $(x-s)(x+s)\equiv 0$. But $p$ is prime, so either $p| x+s$ or $p|x-s$. Therefore $x\equiv \pm s$.

What if we use other representatives

All that we do is completely done at the level of residues modulo $p$. This means that adding multiples of $p$ doesn't affect anything, because it has the effect of adding zeroes. For example, if the central coefficient is $b=-(1+mp)$, then the discriminant changes accordingly $$\Delta = d+2mp+m^2p^2$$ which by the way it is $\equiv d$ modulo $p$.

We have $\Delta\equiv 0$ modulo $p$ if and only if $d\equiv 0$ modulo $p$.

We have $\Delta$ is a quadratic residue modulo $p$ if and only if there is some $s$ such that $s^2\equiv \Delta$ modulo $p$. This means that $s^2\equiv d$ modulo $p$, and so it is equivalent to asking that $d$ is a quadratic residue modulo $p$.

Moreover any choice of $\sqrt \Delta$ is valid as a choice of $\sqrt d$.

The solutions modulo $p$ are still given by the formula

$$x \equiv \frac{1+mp \pm \sqrt \Delta}{2}$$ because in fact it gives the same results, modulo $p$, as the formula $$x \equiv \frac{1 \pm \sqrt d}{2}.$$

Answer 2

Over any field, the roots of higher multiplicity of a polynomial $f(X)$ are the common roots of that polynomial and its (formal) derivative $f'(X)$. This follows because the product rule tells us that the derivative of $(X-a)^2g(X)$ is $2(X-a)g(x)+(X-a)^2g'(X)$, i.e., $a$ is a root of both. (This method works even if the common root is not yet in the field we consider but in a field extension instead)

In the case of $f(X)=X^2-X-c$, we wan a root $f$ has in common with $f'(X)=2X-1$. As long as $p$ is odd, this common root in the field $\Bbb F_p$ can only be the only root o $f'$, namely $\frac12$ -- and that is a root of $f$ iff $f(\frac12)=0$, i.e., iff $\frac14-\frac12-c=0$, or: $c=\frac14$.