Problem 2356

Solution:

Note that the divisibility condition is symmetrical in $m$ and $n$. In other words: If Jana can cross over from island $m$ to island $n$, she can also go the other way. Let us define a graph $G$ as follows: Each of the islands $1,2, \ldots, p$ represents a vertex and we draw an edge between two vertices $m$ and $n$ if and only if
$$p \mid (m^{2}-n+1)(n^{2}-m+1)$$
The edges of our graph now exactly represent between which pairs of islands Jana can travel, so it's easy to see that Jana can travel to every island if and only if $G$ is connected.

This insight motivates us to count the number of edges in $G$, because if we can show that there are less than $p-1$ edges, $G$ has to be disconnected! By the formula
$$|E| = \frac{1}{2} \sum_{v \in V} \operatorname{deg}(v)$$
it is enough to know the number of vertices of every possible degree. The degree of a fixed vertex $m$ is the number of distinct $n \in \{1,2, \ldots, p\}$ such that
$$(m^{2}-n+1)(n^{2}-m+1) \equiv 0 \pmod{p}$$
Obviously, there is exactly one choice for $n$ such that $m^{2}-n+1 \equiv 0 \pmod{p}$, namely $n \equiv m^{2}+1$. But what about $n^{2}-m+1 \equiv 0 \pmod{p}$?

Lemma: Let $p$ be an odd prime and $a$ some residue modulo $p$. Then, $x^{2}-a \equiv 0 \pmod{p}$ has
- no solutions in $x$ for exactly $\frac{p-1}{2}$ different values of $a$.
- exactly one solution in $x$ if and only if $a=0$.
- exactly two solutions in $x$ for $\frac{p-1}{2}$ different values of $a$.

Proof of the Lemma: Note that $x^{2} \equiv y^{2}$ is equivalent to $(x-y)(x+y) \equiv 0$ or in other words $y \equiv \pm x \pmod{p}$.
Hence, the squares of $1, \ldots, \frac{p-1}{2}$ are all distinct modulo $p$ and they are equal to the squares of $p-1, \ldots, \frac{p+1}{2}$, respectively. This gives us $\frac{p-1}{2}$ values of $a$ such that there are two solutions in $x$. The only residue left is $0$, which gives us a unique choice of $a$ with exactly one solution in $x$. The remaining $\frac{p-1}{2}$ values of $a$ therefore admit no solutions at all.

By letting $a = m-1$, the Lemma tells us that there are $\frac{p-1}{2}$ different $m$ with two solutions in $n$. If we assume that the conditions $n^{2}-m+1 \equiv 0 \pmod{p}$ and $m^{2}-n+1 \equiv 0 \pmod{p}$ are never satisfied at the same time (or for $m=n$), we would get
$$|E| = \frac{1}{2} \sum_{v \in V} \operatorname{deg}(v) = \frac{1}{2} \cdot \left(\frac{p-1}{2} \cdot 1 + 1 \cdot 2 + \frac{p-1}{2} \cdot 3\right) = p$$
Sadly, this is not small enough! We need to reduce the number of edges a bit more. The easiest way of doing this is by assuming that there exists a residue $m$ such that $m^{2}-m+1 \equiv 0 \pmod{p}$. This corresponds to a loop in $G$ (an edge going from $m$ to itself), which is irrelevant for the connectivity of $G$. A short calculation inspired by Vieta shows that $m^{2}-m+1 \equiv 0 \pmod{p}$ implies $(1-m)^{2}-(1-m)+1 \equiv 0 \pmod{p}$, so as long as $m \not\equiv 1-m \pmod{p}$, we have two loops, from which we conclude that $G$ is disconnected.

Let us now prove that there are infinitely many primes $p$ such that there exists a residue $m$ satisfying $m^{2}-m+1 \equiv 0 \pmod{p}$: Let $m$ be the product of the first $k$ primes and let $p$ be a prime factor of $m^{2}-m+1$. In particular, $p$ is not equal to the first $k$ primes and so there are infinitely many such $p$. If $m \equiv 1-m \pmod{p}$ then $m \equiv \frac{p+1}{2} \pmod{p}$. However, in this case we must have
$$\left(\frac{p+1}{2}\right)^{2} - \frac{p+1}{2} + 1 = \frac{p^{2}+3}{4} \equiv 0 \pmod{p}$$
which is equivalent to $p=3$. This shows that for all such $p>3$ that we constructed, $G$ is indeed disconnected.

Alternative arguments (inspired by Joel/Mathys): Instead of introducing a simple undirected graph, we introduce a not necessarily simple directed graph where the edge points from $m$ to $n$ if $p \mid m^{2}-n+1$ and from $n$ to $m$ if $p \mid n^{2}-m+1$. The directions are actually completely irrelevant for Jana's travel plans but they allow us to count the edges more elegantly:

For every $m$ there is exactly one value of $n$ such that $m^{2}-n+1 \equiv 0 \pmod{p}$. This means that each of the $p$ vertices has one edge pointing away from it, and therefore we have $p$ edges in total.

To show that the graph is not connected, we will explicitly find two vertices of $G$ which will have loops: Let $p \equiv 1 \pmod{3}$, in particular, $p$ is odd and so $p-1$ is divisible by $6$. Take a primitive root $a$ modulo $p$. For $m = a^{\frac{p-1}{6}}$ we have
$$m^{6}-1 \equiv 0 \pmod{p} \Leftrightarrow (m^{2}-m+1)(m+1)(m^{3}-1) \equiv 0 \pmod{p} \Rightarrow m^{2}-m+1 \equiv 0 \pmod{p}$$
because, since $a$ is a primitive root, $m+1$ and $m^{3}-1$ cannot be divisible by $p$. But the same calculation can be done with $m = a^{\frac{5(p-1)}{6}}$, so we found two loops for infinitely many $p$ (Dirichlet) and we're done!