, 2021

View it as a directed graph with a directed edge $mn$ iff $n = m^2 + 1$ in $\mathbb{Z}_p$. Easy to see that out degree is at most one for every vertex. If $a, b$ are roots of $x^2 - x + 1$, then we can check that $a, b$ are distinct if $p > 3$ (otherwise $a = b = 2^{-1}$ and $1 = 2^{-2}$ in $\mathbb{Z}_p$). So there less than $p-1$ edges, so $p$-Landia is disconnected (as an undirected graph). It remains to show that there are infinitely many $p$ such that there are some $x$ such that $p \mid x^2 - x + 1$. Towards contradiction, suppose $p_1, p_2, \dots, p_k$ are the only primes such that $x^2 - x + 1 \equiv 0 \pmod p$ has solutions. Consider $x = p_1p_2 \cdots p_k$ and let $p$ be a prime factor of $x^2 - x + 1$, clearly $x^2 - x + 1 \equiv 0 \pmod p$ and $x^2 - x + 1 \equiv 1 \pmod {p_i}$ for $i = 1, 2, \dots, p_k$, contradict to the assumption.