BdMO Online Forum

For each prime $p$, there is a kingdom of $p$-Landia consisting of $p$ islands numbered $1, 2,\dots, p$. Two distinct islands numbered $n$ and $m$ are connected by a bridge if and only if $p$ divides $(n^2-m + 1)(m^2-n + 1)$. The bridges may pass over each other, but cannot cross. Prove that for infinitely many $p$ there are two islands in $p$-Landia not connected by a chain of bridges.