Problem 3

Let  k  be a positive integer and let S  be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of S  around the circle such that the product of any two neighbours is of the form x2+x+k  for some positive integer  k.

Solution

We'll prove this by induction on $|S|$ on the relaxed problem: we'll prove the statement such that product of any two neighbors is of the form $x^2 + x + k$ for some integer $x$, which proves the original problem. The result is clearly true for $|S| \le 3$. Now, assume that the result is true for any $|S| < n$, where $n \ge 4$. We'll prove that this is true for $|S| = n$. Indeed, suppose that there exists a configuration for $S$ with $|S| = n$, otherwise we are done. Call a number $m$ of the form $m = x^2 + x + k$ for some $x \in \mathbb{Z}$ as nice. Now, take the largest prime $P$ on this set $S$. By assumption, there exists distinct primes $Q, R < P$ such that
\[ PQ = x^2 + x + k \ \text{and} \ PR = y^2 + y + k \]

Claim 01. $QR$ is nice.
Proof. By maximality of $P$, we have $x, y < P$ and furthermore

\[ P \mid x^2 - y^2 + x - y = (x - y)(x + y + 1) \implies x \equiv y \pmod{P} \ \text{or} \ x + y + 1 \equiv 0 \pmod{P} \]As $x \not= y$, we conclude that $x + y = P - 1$. Now, we have
\[ 2(k - xy) \equiv (x + y)^2 - 2xy + (x + y) + 2k \equiv (x^2 + x + k) + (y^2 + y + k) \equiv 0 \pmod{P} \]and since $P$ is odd, then $xy \equiv k \pmod{P}$. Write $xy = k + Pz$ for some $z \in \mathbb{Z}$.
Therefore, we have
\begin{align*} QR &= \frac{(PQ)(PR)}{P^2} \\ &= \frac{(x^2 + x + k)(y^2 + y + k)}{P^2} = \frac{(x^2 + x + xy - Pz)(y^2 + y + xy - Pz)}{P^2} = \frac{(Px - Pz)(Py - Pz)}{P^2} \\ &= (x - z)(y - z) = xy - z(x + y) + z^2 = k + Pz - z(x + y) + z^2 = k + z + z^2 \end{align*}We thus conclude that $QR$ has to be nice as well.

The above claim implies that we can construct a valid configuration with $|S| = n - 1$ assuming that a valid configuration with $|S| = n$ exists; and by inductive hypothesis, there exists a unique valid configuration for $|S| = n - 1$, by deleting the largest prime. Therefore, the valid configuration for $|S| = n$ can only be obtained by inserting $P$ between any two consecutive primes in the configuration for $|S| = n - 1$. Now, suppose there are more than one ways to insert the prime, then there exists distinct $a,b,c \in S$ and $x,y,z \in \mathbb{N}$ such that
\begin{align*} aP &= x^2 + x + k \\ bP &= y^2 + y + k \\ cP &= z^2 + z + k \end{align*}However, as $a,b,c < P$, we have $x,y,z < P$ as well. Furthermore, as $a,b,c$ are distinct, then $x,y,z$ are distinct as well. Therefore, $P \mid x + y + 1, y + z + 1 \implies x + y = P - 1 = y + z \implies x = z$, a contradiction. Therefore, the configuration for $|S| = n$ has to be unique as well, and hence our original result holds.