Proof. We argue by induction on N. The assertion is clear for $N\leq 1$ . Put $z=x_{N-1}$ and $S=R[x_0,\ldots ,x_{N-2}]$ . We first prove that

$$ \begin{align*} P(z):=\prod_{i=0}^{N-2}(z-x_i) \end{align*} $$

divides G in $S[z]$ . Suppose that, for some k with $0\leq k\leq N-2$ , we have already written

$$ \begin{align*} G=\prod_{i=0}^{k-1}(z-x_i)G_k \quad(G_k\in S[z]), \end{align*} $$

with the empty product understood as $1$ . Since G is zero after the specialisation $z=x_k$ ,

$$ \begin{align*} 0=\prod_{i=0}^{k-1}(x_k-x_i)\,G_k|_{z=x_k}. \end{align*} $$

The product $\prod _{i=0}^{k-1}(x_k-x_i)$ is monic as a polynomial in $x_k$ and, hence, is a non-zero-divisor. Therefore, $G_k|_{z=x_k}=0$ , so the monic factor theorem gives $G_k=(z-x_k)G_{k+1}$ for some $G_{k+1}\in S[z]$ . Repeating this for $k=0,1,\ldots ,N-2$ , we obtain

$$ \begin{align*} G=P(z)H \quad(H\in S[z]). \end{align*} $$

It remains to apply the induction hypothesis to H in the variables $x_0,\ldots ,x_{N-2}$ . If $0\leq r<s\leq N-2$ and we set $x_s=x_r$ , then the corresponding specialisation of G is zero. Since the corresponding specialisation of $P(z)$ is monic in z, it is a non-zero-divisor; hence, the corresponding specialisation of H is zero. Thus, H is alternating in $x_0,\ldots ,x_{N-2}$ in the same sense. By induction,

$$ \begin{align*} \prod_{0\le r<s\le N-2}(x_s-x_r) \end{align*} $$

divides H. Multiplying this divisor by $P(z)$ gives the required Vandermonde product for $x_0,\ldots ,x_{N-1}$ .

Proof. Put

$$ \begin{align*} F(X,Y)=(X^2+cXY+dY^2)^{n-2} \end{align*} $$

and consider the polynomial determinant

$$ \begin{align*} \Phi(\mathbf x,\mathbf y)= \det [F(x_i,y_j)]_{0\leq i,j\leq n-1} \in \mathbb Z[x_0,\ldots,x_{n-1},y_0,\ldots,y_{n-1}]. \end{align*} $$

If two x-variables are made equal, then the corresponding two rows are equal; hence, $\Phi $ is alternating in $x_0,\ldots ,x_{n-1}$ in the sense of Lemma 2.1. Applying that lemma over $\mathbb Z[y_0,\ldots ,y_{n-1}]$ , we find that

$$ \begin{align*} V(\mathbf x):=\prod_{0\leq r<s\leq n-1}(x_s-x_r) \end{align*} $$

divides $\Phi $ . Thus,

$$ \begin{align*} \Phi(\mathbf x,\mathbf y)=V(\mathbf x)\Phi_1(\mathbf x,\mathbf y) \end{align*} $$

for some

$$ \begin{align*} \Phi_1\in\mathbb Z[x_0,\ldots,x_{n-1},y_0,\ldots,y_{n-1}]. \end{align*} $$

If two y-variables are made equal, then the corresponding two columns of $\Phi $ are equal. Since $V(\mathbf x)$ is independent of the y-variables and nonzero in the integral domain under consideration, cancellation shows that $\Phi _1$ is alternating in $y_0,\ldots ,y_{n-1}$ in the same sense. Applying Lemma 2.1 again, now over $\mathbb Z[x_0,\ldots ,x_{n-1}]$ , gives

$$ \begin{align*} \Phi(\mathbf x,\mathbf y)=V(\mathbf x)V(\mathbf y)H(\mathbf x,\mathbf y) \end{align*} $$

for some $H\in \mathbb Z[x_0,\ldots ,x_{n-1},y_0,\ldots ,y_{n-1}]$ , where

$$ \begin{align*} V(\mathbf y)=\prod_{0\leq r<s\leq n-1}(y_s-y_r). \end{align*} $$

Specialising $x_i=y_i=i$ yields

(2.1) $$ \begin{align} D_n(c,d)=V_n^2\,H(0,1,\ldots,n-1,0,1,\ldots,n-1), \end{align} $$

where

$$ \begin{align*} V_n=\prod_{0\leq r<s\leq n-1}(s-r)=\prod_{k=1}^{n-1}k^{\,n-k}. \end{align*} $$

It remains to prove that $n\mid V_n$ .

Let $p^\alpha \parallel n$ . The difference $s-r=p$ occurs for exactly $n-p$ pairs of integers $(r,s)$ with ${0\le r<s\le n-1}$ , and hence,

$$ \begin{align*} \nu_p(V_n)\ge n-p. \end{align*} $$

We claim that $n-p\ge \alpha $ . It suffices to show that the set

$$ \begin{align*} \{p,p+1,p+2,\ldots,n\} \end{align*} $$

has at least $\alpha +1$ elements. Indeed, the $\alpha +1$ elements

$$ \begin{align*} p,\ p+1,\ p^2,\ p^3,\ldots,\ p^\alpha \end{align*} $$

with the evident omission of $p^2,\ldots ,p^\alpha $ when $\alpha =1$ , are distinct elements of this set. Here, $p^\alpha \leq n$ ; and when $\alpha =1$ , the compositeness of n and the divisibility $p\mid n$ give $n\ge 2p\ge p+1$ . Thus, $n-p+1\ge \alpha +1$ , proving the claim. Therefore, $\nu _p(V_n)\ge \alpha $ for every prime power $p^\alpha \parallel n$ . Hence, $n\mid V_n$ , and (2.1) shows $n^2\mid D_n(c,d)$ .

Proof. Let

$$ \begin{align*} UAV=\operatorname{diag}(s_1,\ldots,s_N) \end{align*} $$

be a Smith normal form of A, where $U,V$ are unimodular integer matrices. The reductions of U and V modulo p are invertible over $\mathbb F_p$ and, hence, multiplication by them preserves rank over $\mathbb F_p$ . Thus, the rank of A modulo p is the number of diagonal entries $s_i$ whose residue modulo p is nonzero. If this rank is at most $N-r$ , then at least r of the $s_i$ are divisible by p. Consequently,

$$ \begin{align*} p^r\mid s_1\cdots s_N=\det\,(UAV)=\pm\det\,A, \end{align*} $$

as required. If some $s_i=0$ , the conclusion is of course still valid.

Proof. We still write c and d for their residues modulo p, and put

$$ \begin{align*} f(T)=T^2+cT+d\in\mathbb F_p[T]. \end{align*} $$

The assumption $({d}/{p})=-1$ implies $d\ne 0$ in $\mathbb F_p$ . Define

$$ \begin{align*} S=\sum_{t\in\mathbb F_p^\times} f(t)^{p-2}t^{-m}. \end{align*} $$

Here and in the following, negative powers are interpreted in the multiplicative group $\mathbb F_p^\times $ . By (3.1),

$$ \begin{align*} S=\sum_{a=0}^{2p-4}\alpha_a \sum_{t\in\mathbb F_p^\times}t^{a-m}. \end{align*} $$

For any integer k, the usual orthogonality relation on $\mathbb F_p^\times $ gives

$$ \begin{align*} \sum_{t\in\mathbb F_p^\times}t^k= \begin{cases} -1 & \text{if } p-1\mid k, \\ 0 & \text{if } p-1\nmid k, \end{cases} \quad\text{in }\mathbb F_p. \end{align*} $$

Among the integers a with $0\le a\le 2p-4$ , the only ones congruent to m modulo $p-1$ are $a=m$ and $a=m+p-1$ . Hence,

(3.2) $$ \begin{align} S=-(\alpha_m+\alpha_{m+p-1}). \end{align} $$

Now, the map $t\mapsto d/t$ is a permutation of $\mathbb F_p^\times $ . Moreover,

$$ \begin{align*} f(d/t)=d\,t^{-2}f(t) \end{align*} $$

for every $t\in \mathbb F_p^\times $ . Therefore,

$$ \begin{align*} f(d/t)^{p-2}(d/t)^{-m} = (d\,t^{-2})^{p-2}f(t)^{p-2}d^{-m}t^m = d^{-m-1}t^{m+2}f(t)^{p-2}. \end{align*} $$

Since

$$ \begin{align*} m+2=(p+1)/2\equiv -m \pmod {p-1} \end{align*} $$

and, by Euler’s criterion,

$$ \begin{align*} d^{-m-1} =d^{-(p-1)/2} =(d^{(p-1)/2})^{-1} =\bigg(\frac{d}{p}\bigg)^{-1} =-1 \quad\text{in }\mathbb F_p, \end{align*} $$

we obtain

$$ \begin{align*} f(d/t)^{p-2}(d/t)^{-m} =-f(t)^{p-2}t^{-m} \end{align*} $$

for all $t\in \mathbb F_p^\times $ . Summing over $t\in \mathbb F_p^\times $ and noting that $t\mapsto d/t$ is a permutation gives $S=-S$ . Since p is odd, $S=0$ . Equation (3.2) now gives the desired cancellation.

Proof. First, note the uniqueness in the statement. If a polynomial of degree at most $p-1$ in each variable vanishes on $\mathbb F_p^2$ , then, after fixing $Y=y\in \mathbb F_p$ , it is a polynomial in X of degree at most $p-1$ with p roots; hence, it is zero. Its coefficients, as polynomials in Y, again have degree at most $p-1$ and vanish at all $y\in \mathbb F_p$ , and therefore are zero. Existence follows by applying one-variable Lagrange interpolation successively in the two variables.

Let the coefficients $\alpha _a$ be defined by (3.1). We have the homogeneous expansion

(3.3) $$ \begin{align} (X^2+cXY+dY^2)^{p-2} =\sum_{a=0}^{2p-4}\alpha_a X^aY^{2p-4-a}. \end{align} $$

For $e\ge 0$ , put $\bar e=0$ if $e=0$ and, otherwise, let $\bar e$ be the unique integer in $\{1,\ldots ,p-1\}$ congruent to e modulo $p-1$ . Then, $z^e=z^{\bar e}$ for all $z\in \mathbb F_p$ . Since every monomial in (3.3) has total degree $2p-4<2p-2$ , the two exponents in the same monomial cannot both be at least p. Thus, at most one exponent in each monomial needs reduction to transform the right-hand side of (3.3) into $R(X,Y)$ . This is the point at which we use $p>3$ ; for example, the reduction of $Y^{2p-4}$ to $Y^{p-3}$ requires $p-3\in \{1,\ldots ,p-1\}$ .

We now record the reduction explicitly. First, the term $a=0$ gives $\alpha _0Y^{p-3}$ . For ${1\le r\le p-4}$ , the two indices $a=r$ and $a=r+p-1$ both reduce to the same monomial

$$ \begin{align*} X^rY^{p-3-r}. \end{align*} $$

The three boundary indices $a=p-3,p-2,p-1$ give respectively

$$ \begin{align*} \alpha_{p-3}X^{p-3}Y^{p-1},\quad \alpha_{p-2}X^{p-2}Y^{p-2}\quad\text{and}\quad \alpha_{p-1}X^{p-1}Y^{p-3}. \end{align*} $$

Finally, since $\alpha _{2p-4}=1$ , the index $a=2p-4$ gives $X^{p-3}$ . Hence, the same function on $\mathbb F_p^2$ is represented by

(3.4) $$ \begin{align} R(X,Y)={}&\alpha_0Y^{p-3} +\sum_{r=1}^{p-4}(\alpha_r+\alpha_{r+p-1})X^rY^{p-3-r} +X^{p-3} \nonumber\\ &+\alpha_{p-3}X^{p-3}Y^{p-1} +\alpha_{p-2}X^{p-2}Y^{p-2} +\alpha_{p-1}X^{p-1}Y^{p-3}. \end{align} $$

Let $m=(p-3)/2$ . Since $p>3$ , we have $1\le m\le p-4$ . In (3.4), the only possible nonzero entry in row m of C is

$$ \begin{align*} C_{m,p-3-m}=\alpha_m+\alpha_{m+p-1}, \end{align*} $$

and this is zero by Lemma 3.2. Hence, row m is zero. In addition, row $0$ and row $p-1$ can have nonzero entries only in column $p-3$ , so these two rows are linearly dependent. These rows are distinct from row m. Consequently, the row rank of C is at most $p-2$ .

Proof. Let $a_i$ denote the residue class of i in $\mathbb F_p$ . Let

$$ \begin{align*} M=[(a_i^2+ca_ia_j+da_j^2)^{p-2}]_{0\le i,j\le p-1} \end{align*} $$

be the reduction modulo p of the integer matrix defining $D_p(c,d)$ . Here, c and d are also viewed modulo p. By Lemma 3.1, it is enough to prove that

$$ \begin{align*} \text{rank}_{\mathbb F_p}M\le p-2. \end{align*} $$

Let $R(X,Y)$ and $C=(C_{r,s})$ be as in Lemma 3.3. Since R represents the same function on $\mathbb F_p^2$ as $(X^2+cXY+dY^2)^{p-2}$ , we have

$$ \begin{align*} M=[R(a_i,a_j)]_{0\le i,j\le p-1}. \end{align*} $$

Set

$$ \begin{align*} V=(a_i^r)_{0\le i,r\le p-1}. \end{align*} $$

Then,

$$ \begin{align*} M=VCV^{\mathrm t}. \end{align*} $$

Hence,

$$ \begin{align*} \text{rank}_{\mathbb F_p}M\leq\text{rank}_{\mathbb F_p}C\le p-2 \end{align*} $$

by Lemma 3.3. Lemma 3.1, with $N=p$ and $r=2$ , now yields $p^2\mid D_p(c,d)$ .

Proof of Theorem 1.1.

If n is composite, the assertion follows from Proposition 2.2. If n is prime, then the assumption in the theorem is precisely $({d}/{n})=-1$ as a Legendre-symbol condition, and Proposition 3.4 applies.