[proofplan] We reduce the problem to finding a nonzero of a polynomial: we need distinct $a_1, \ldots, a_{p-1} \in \mathbb{Z}_p$ such that the values $a_i + b_i$ are also pairwise distinct, and the last entries $a_p$ and $c_p$ are forced by the enumeration condition and $\sum b_i = 0$. The polynomial $f = \prod_{i < j}(X_i - X_j)(X_i + b_i - X_j - b_j)$ vanishes exactly when either the $a_i$ or the $a_i + b_i$ collide. Its total degree is $(p-1)(p-2)$, and we apply [Alon's Combinatorial Nullstellensatz](/theorems/2617) with sets $S_i$ of size $p - 1$. The coefficient of $X_1^{p-2} \cdots X_{p-1}^{p-2}$ reduces to the coefficient of the "flat" monomial in the square of the Vandermonde, which we compute via a permutation-pairing argument and Wilson's theorem. [/proofplan] [step:Reduce to finding distinct $a_1, \ldots, a_{p-1}$ with distinct sums $a_i + b_i$] It suffices to find pairwise distinct elements $a_1, \ldots, a_{p-1} \in \mathbb{Z}_p$ such that the $p - 1$ values $c_i := a_i + b_i$ for $i = 1, \ldots, p - 1$ are also pairwise distinct. To see why: once such $a_1, \ldots, a_{p-1}$ are found, define $a_p$ to be the unique element of $\mathbb{Z}_p \setminus \{a_1, \ldots, a_{p-1}\}$ and $c_i = a_i + b_i$ for all $i$. The $a_i$ for $i = 1, \ldots, p$ form a permutation of $\mathbb{Z}_p$ by construction. For the $c_i$: since $\sum_{i=1}^p b_i = 0$ in $\mathbb{Z}_p$, \begin{align*} \sum_{i=1}^p c_i = \sum_{i=1}^p a_i + \sum_{i=1}^p b_i = \sum_{i=1}^p a_i. \end{align*} Both sums $\sum a_i$ and $\sum c_i$ equal $0 + 1 + \cdots + (p-1) = p(p-1)/2$. Since $c_1, \ldots, c_{p-1}$ are $p - 1$ distinct elements of $\mathbb{Z}_p$, the value $c_p$ is determined by the sum constraint, and it must be the unique element of $\mathbb{Z}_p \setminus \{c_1, \ldots, c_{p-1}\}$. Therefore $c_1, \ldots, c_p$ is also a permutation of $\mathbb{Z}_p$. [guided] The reduction eliminates the last index $p$ entirely: we only need to arrange $p - 1$ of the $p$ pairs, and the constraint $\sum b_i = 0$ automatically forces the last pair into place. This is because both the $a$-enumeration and the $c$-enumeration are permutations of $\mathbb{Z}_p$, which have the same element sum $0 + 1 + \cdots + (p-1)$. If $p - 1$ of the $c$-values are distinct, the $p$-th is determined by the sum, and since it must complete the permutation, it is forced to be the missing element. Why work with $p - 1$ variables rather than $p$? The Nullstellensatz requires $\deg f = \sum d_i$. With $p$ variables and all pairwise distinctness conditions, $\deg f = 2\binom{p}{2} = p(p-1)$, and $\sum d_i = p(p-1)$ forces $d_i = p - 1$ and $|S_i| = p$. But the coefficient of $X_1^{p-1} \cdots X_p^{p-1}$ in the associated polynomial is harder to control. With $p - 1$ variables, the degree $(p-1)(p-2)$ matches $\sum d_i$ for $d_i = p - 2$ and $|S_i| = p - 1$, and the coefficient computation reduces to the square of the Vandermonde, which is tractable. [/guided] [/step] [step:Build the polynomial whose nonzeros give distinct sequences] Define \begin{align*} f(X_1, \ldots, X_{p-1}) = \prod_{1 \leq i < j \leq p-1} (X_i - X_j)(X_i + b_i - X_j - b_j) \in \mathbb{Z}_p[X_1, \ldots, X_{p-1}]. \end{align*} A point $(x_1, \ldots, x_{p-1}) \in \mathbb{Z}_p^{p-1}$ satisfies $f(x_1, \ldots, x_{p-1}) \neq 0$ if and only if: - $x_i \neq x_j$ for all $i < j$ (from the factors $(X_i - X_j)$), ensuring $x_1, \ldots, x_{p-1}$ are pairwise distinct; - $x_i + b_i \neq x_j + b_j$ for all $i < j$ (from the factors $(X_i + b_i - X_j - b_j)$), ensuring the sums $x_i + b_i$ are pairwise distinct. The total degree is $\deg f = 2\binom{p-1}{2} = (p-1)(p-2)$. [/step] [step:Set up the Nullstellensatz with sets of size $p - 1$] With $S_i = \mathbb{Z}_p$ we would have $\sum d_i = (p-1)^2 > (p-1)(p-2) = \deg f$, so the degree condition fails. Instead, for each $i = 1, \ldots, p - 1$, choose any subset $S_i \subseteq \mathbb{Z}_p$ with $|S_i| = p - 1$. Set $d_i = |S_i| - 1 = p - 2$. Then \begin{align*} \sum_{i=1}^{p-1} d_i = (p-1)(p-2) = \deg f. \end{align*} The target monomial is $X_1^{p-2} \cdots X_{p-1}^{p-2}$. [guided] By reducing each $|S_i|$ by $1$ (from $p$ to $p - 1$), each $d_i$ drops from $p - 1$ to $p - 2$, and $\sum d_i$ decreases by $p - 1$, from $(p-1)^2$ to $(p-1)(p-2) = \deg f$. The specific element excluded from each $S_i$ does not affect the coefficient computation, and any nonzero of $f$ on $S_1 \times \cdots \times S_{p-1}$ is a fortiori a nonzero on $\mathbb{Z}_p^{p-1}$. [/guided] [/step] [step:Compute the coefficient of $X_1^{p-2} \cdots X_{p-1}^{p-2}$ via a Vandermonde pairing] The leading homogeneous part of each factor $(X_i + b_i - X_j - b_j)$ is $(X_i - X_j)$, so the coefficient of $X_1^{p-2} \cdots X_{p-1}^{p-2}$ in $f$ equals the coefficient of the same monomial in \begin{align*} V^2 = \Bigl(\prod_{1 \leq i < j \leq p-1} (X_i - X_j)\Bigr)^2, \end{align*} where $V = \prod_{i < j}(X_i - X_j)$ is the Vandermonde product in $p - 1$ variables. Write $m = p - 1$. The Vandermonde product $V$ equals the determinant $\det(X_j^{i-1})_{1 \leq i,j \leq m}$, which expands as \begin{align*} V = \sum_{\sigma \in S_m} \operatorname{sgn}(\sigma) \prod_{i=1}^m X_i^{\sigma(i) - 1}. \end{align*} Therefore \begin{align*} V^2 = \sum_{\sigma, \tau \in S_m} \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau) \prod_{i=1}^m X_i^{\sigma(i) + \tau(i) - 2}. \end{align*} The monomial $X_1^{m-1} \cdots X_m^{m-1} = X_1^{p-2} \cdots X_{p-1}^{p-2}$ requires $\sigma(i) + \tau(i) - 2 = m - 1$ for every $i$, i.e., $\sigma(i) + \tau(i) = m + 1$ for all $i$. Define the reversal permutation $\omega \in S_m$ by $\omega(k) = m + 1 - k$. The condition $\tau(i) = m + 1 - \sigma(i) = \omega(\sigma(i))$ means $\tau = \omega \circ \sigma$. So for each $\sigma \in S_m$ there is exactly one $\tau$ contributing to the coefficient, namely $\tau = \omega \circ \sigma$. The coefficient is \begin{align*} [X_1^{p-2} \cdots X_{p-1}^{p-2}]\, V^2 &= \sum_{\sigma \in S_m} \operatorname{sgn}(\sigma) \operatorname{sgn}(\omega \circ \sigma) \\ &= \sum_{\sigma \in S_m} \operatorname{sgn}(\sigma) \cdot \operatorname{sgn}(\omega) \cdot \operatorname{sgn}(\sigma) \\ &= \operatorname{sgn}(\omega) \sum_{\sigma \in S_m} \operatorname{sgn}(\sigma)^2 \\ &= \operatorname{sgn}(\omega) \cdot m! \end{align*} since $\operatorname{sgn}(\sigma)^2 = 1$ for every permutation. The reversal $\omega$ swaps $k \leftrightarrow m + 1 - k$ for $k = 1, \ldots, m$. This is a product of $\lfloor m/2 \rfloor$ disjoint transpositions, so $\operatorname{sgn}(\omega) = (-1)^{\lfloor m/2 \rfloor} = (-1)^{(p-1)/2}$ (since $m = p - 1$ is even, $\lfloor m/2 \rfloor = (p-1)/2$). By Wilson's theorem, $m! = (p-1)! \equiv -1 \pmod{p}$. Therefore \begin{align*} [X_1^{p-2} \cdots X_{p-1}^{p-2}]\, V^2 = (-1)^{(p-1)/2} \cdot (p-1)! \equiv (-1)^{(p-1)/2} \cdot (-1) = (-1)^{(p+1)/2} \pmod{p}, \end{align*} which is $\pm 1$ and in particular nonzero in $\mathbb{Z}_p$. [guided] The key idea is to use the determinantal expansion of the Vandermonde. Writing $V = \sum_\sigma \operatorname{sgn}(\sigma) \prod X_i^{\sigma(i)-1}$ and squaring, the coefficient of the "flat" monomial $\prod X_i^{m-1}$ involves only those pairs $(\sigma, \tau)$ with $\sigma(i) + \tau(i) = m + 1$ for all $i$. This pins down $\tau$ as $\omega \circ \sigma$, where $\omega$ is the reversal permutation. Why does this pairing work so cleanly? Because the exponent vector $(m-1, m-1, \ldots, m-1)$ is the sum of the "staircase" vector $(0, 1, \ldots, m-1)$ with its reversal $(m-1, m-2, \ldots, 0)$. The Vandermonde determinant produces exactly these staircase monomials (one per permutation), and squaring it pairs each staircase with its complement. The sign computation uses the multiplicativity of $\operatorname{sgn}$: $\operatorname{sgn}(\omega \circ \sigma) = \operatorname{sgn}(\omega) \cdot \operatorname{sgn}(\sigma)$, and then $\operatorname{sgn}(\sigma)^2 = 1$ collapses the sum to $\operatorname{sgn}(\omega) \cdot |S_m|$. Wilson's theorem converts $(p-1)!$ to $-1$ modulo $p$, giving a final answer of $\pm 1 \neq 0$. [/guided] [/step] [step:Apply the Nullstellensatz and conclude] The polynomial $f \in \mathbb{Z}_p[X_1, \ldots, X_{p-1}]$ has degree $(p-1)(p-2) = \sum_{i=1}^{p-1} d_i$ with $d_i = p - 2$, and the coefficient of $X_1^{p-2} \cdots X_{p-1}^{p-2}$ is $(-1)^{(p+1)/2} \neq 0$ in $\mathbb{Z}_p$. By [Alon's Combinatorial Nullstellensatz](/theorems/2617) applied with $|S_i| = p - 1 = d_i + 1$, there exists $(a_1, \ldots, a_{p-1}) \in S_1 \times \cdots \times S_{p-1} \subseteq \mathbb{Z}_p^{p-1}$ with $f(a_1, \ldots, a_{p-1}) \neq 0$. This means $a_1, \ldots, a_{p-1}$ are pairwise distinct and the sums $a_1 + b_1, \ldots, a_{p-1} + b_{p-1}$ are pairwise distinct. By the reduction in the first step, setting $a_p$ to be the remaining element of $\mathbb{Z}_p$ and $c_i = a_i + b_i$ yields enumerations $a_1, \ldots, a_p$ and $c_1, \ldots, c_p$ of $\mathbb{Z}_p$ with $a_i + b_i = c_i$ for all $i$. [/step]