We say that $m$ points to $n$ if $m^2+1\equiv n \pmod p$. Pick a huge prime $p\equiv 7 \pmod {12}$. Henceforth work entirely in $\mathbb F_p$. It's well know that $\exists a,b$ such that $a,b$ they are the roots of the equation $x^2-x+1=0.$ Note that $-a$ is the only element pointing towards $a$ and similarly $-b$ is the unique element pointing towards $b$. Claim : Atleast one of $-1-a$ and $-1-b$ is a NQR mod $p$. We have $(-1-a)(-1-b)=(-1)^2-1+1=3$. So, we have : $$ \left( \frac {(-1-a)((-1-b)}{p}\right)= \left( \frac 3p \right) = -1$$ Hence one of $-1-a,-1-b$ is a NQR, say the former. This means that the equation $x^2+1=-a$ has no solution, hence, no element points towards $-a$. Hence $a,-a$ are isolated from the rest of the elements. $\square$

We consider all indices modulo $p$. First of all we need to show that $G_{p}$ has exactly $p$ edges. Define a directed graph $G'_{p}$ by $m\mapsto m^{2}+1$ for $m=1,...,m$ without other edges. Then $G'_{p}$ obviously has $p$ edges. These coincide with the edges of $G_{p}$ by definition. It is well-known that a connected graph on $p$ vertices must have at least $p-1$ edges. The vertex $m$ is connected to itself if and only if $$m^{2}-m+1\equiv 0\;\; (\text{mod}\;p).$$We now claim that if $p$ divides $k^{2}-k+1$ and $k \not \equiv \frac{p+1}{2}$ (mod $p$), then $G_{p}$ is not connected. Indeed, a short calculation shows that $p$ also divides $(p-k+1)^{2}-(p-k+1)+1$ and we have $p-k+1\not \equiv k$ (mod $p$) due to the second condition. Hence we have found two loops, which shows that $G_{p}$ is disconnected. It remains to prove that there are infinitely many such primes. Note that if $p|k^{2}-k+1$ and $k \equiv \frac{p+1}{2}$ (mod $p$), then $0\equiv \left(\frac{p+1}{2}\right)^{2}-\frac{p+1}{2}+1\equiv \frac{p^{2}+3}{4}$ (mod $p$), which can only happen for $p=3$. Let now $p_{1}=7$ (we can check that $G_{7}$ is disconnected) and define $p_{k+1}$ to be any prime divisor of $$\left(3\cdot\prod_{i=1}^{k}p_{i}\right)^{2}-\left(3\cdot\prod_{i=1}^{k}p_{i}\right)+1.$$Then $p_{k+1}$ is different from $3,p_{1},...,p_{k}$ and moreover $G_{p_{k+1}}$ is not connected by the claim above. This finishes the proof.

I got a 0.9 style score on this one. I claim that for all $p\equiv 7 \pmod{12}$, $G_p$ is disconnected. We will work mod p instead of on $\{1,2,\ldots p\}$. Consider a generator $g\pmod{p}$. then, let \[a=g^{\frac{p-1}{3}}\text{ and }b=g^{2\cdot \frac{p-1}{3}}\]I claim that one of $a-1$ or $b-1$ is not a quadratic residue mod $p$. Consider \[(a-1)(b-1)=ab-a-b+1=g^{p-1}-g^{(p-1)/3}-g^{2(p-1)/3}+1 \equiv 3-(1+g^{(p-1)/3}+g^{2(p-1)/3})\]\[\equiv 3 - \frac{g^{p-1}-1}{g^{\frac{p-1}{3}}}\equiv 3-0]equiv 3 \pmod{p}\]Since $p\equiv 3 \pmod{4}$, and $3\equiv 3 \pmod{4}$, by QR, \[\left(\frac{3}{p}\right)= - \left(\frac{p}{3}\right)= -\left(\frac{1}{3}\right)=-1\]Thus, 3 isn't a square mod $p$, so one of $a-1$ or $b-1$ isn't a square mod $p$ because if they were both squares, 4 would be the product of 2 squares, which is also a square contradiction. WLOG say that $a-1$ isn't a quadratic residue mod $p$. We only need the fact that $a^2+a+1\equiv b^2+b+1\equiv 0$. Then, I claim that the pair of vertices $(a,p-a)$ are disconnected from the rest of the graph. Case 1: There exists an edge between $a$ and $x\neq a,p-a$. Since $p\mid (a^2+a-x)(x^2+a-a)$, either $p\mid a^2+1-x$ or $p\mid x^2+1-a$. In case 1a, $p\mid a^2+1-x$. Thus, \[x\equiv a^2+1\equiv (a^2+a+1)-a\equiv -a \pmod{p}\]Note: we are using $a^2+a+1\equiv g^{2\frac{p-1}{3}}+g^{\frac{p-1}{3}}+1\equiv 0 \pmod{p}$, and will use it w/o proof. Thus, $x\equiv p-a$, contradiction.$\square$ In case 1b, $p\mid x^2+1-a$. Thus, \[x^2\equiv a-1 \pmod{p}\]which is absurd because $a-1$ is not a quadratic residue.$\square$ Case 2: There exist an edge between $p-a$ and $y\neq a,p-a$. Since $p\mid ((p-a)^2+1-y))(x^2+1-(p-a))$, $p$ must divide one of the terms. Case 2a: $p\mid (p-a)^2+1-y$. Then, \[y\equiv (p-a)^2+1\equiv a^2+1\equiv -a \pmod{p}\]Thus, $y\equiv p-a$, contradiction. $\square$. Case 2b: $p\mid x^2+1-(p-a)$. Then, \[x^2\equiv (p-a)-1\equiv -a-1\equiv a^2 \pmod{p}\]Thus, \[p\mid x^2-a^2\Longrightarrow p\mid x-a \text{ or } p\mid x+a\]Thus, either $x\equiv a$ or $x\equiv p-a$, either way contradiction. $\square$. THus, we have shown that no edges from elsewhere in $G_p$ go to the pair $a,p-a$ and have also verified the existence of $a$ for all $p\equiv 7 \pmod{12}$. By Dirichlet's there are infinitely many such $p$, thus $G_p$ is disconnected for such $p$ and there are clearly infinitely many $p$ such that $G_p$ is disconnected. $\blacksquare$.

Draw a directed graph with an edge $m\to n$ if $n\equiv m^2+1 \pmod{p}$. Claim: There are two self-loops in this graph. Proof: There is a self loop at $x$ iff $x^2\equiv x+1 \pmod{p}$, i.e. $x^3\equiv -1 \pmod{p}$ but $x\not \equiv -1 \pmod{p}$. Now for $p\equiv 1\pmod{6}$, choose a primitive root $g$, and there is a self-loop at $g^{\tfrac{p-1}{6}}$ and at $g^{\tfrac{5(p-1)}{6}}$. $\blacksquare$ Note that every vertex has outdegree $1$. Combining all these, hence in the undirected sense, there are at most $p-2$ edges, which must be disconnected since a connected graph has at least $p-1$ edges.

Nice problem. Here's the sketch of my solution during TST. Actually a stronger bound for $\# \text{edges}$ is posssible. $\bullet\hspace{2 mm}$ Translate everything into gt language, where our graph is undirected. $\bullet\hspace{2 mm}$ Now a vertex $v$ has degree $1$ or $3$ if $v-1$ is a QR and if it's not etc. Choose $p\equiv 3\pmod 4$ to reduce the degrees of $1, p$. and compute them separately later. Also choose $p\equiv 1\pmod 6$ to get $2$ distinct self-loops. $\bullet\hspace{2 mm}$ Observe that there're at most $p-3$ edges.

This problem was proposed by Marius Fischer, Denmark.

The original wording was fascinating.... But really nice and simple problem - It is not hard to deduce that if $\left(\frac{m-1}{p} \right) = 1$ , then $deg(m) = 3$ , except in the case when $ m - 1 \equiv (m^2 + 1)^2 $ $ mod p $ , in which $deg(m) = 2$ , and if $\left(\frac{m-1}{p} \right) = -1 $ then $deg(m) = 1$ . Now choose $p \equiv$ $3$ $ mod 4 $ No of$ $QR$ $=No of$NQR's$. as $-1$ will be a $NQR$ So $\sum { deg(v_i)}$ is atmost $$ 3 \left(\frac{p-1}{2} - 2 \right) + \left(\frac{p-1}{2} \right) + 2(2) = 2p-1$$so by handshaking lemma No of $edges$ is atmost $\left(\frac{2p-1}{2} \right) \le p-2$ , which is less than number of vertices. So some vertex must be isolated and we are done. $\blacksquare$

Below is an elementary proof: We will prove a more stronger result that there are infinitely many $p$ for which the graph $G_p$ has at most $p-2$ edges. Claim : There exist infinitely many odd primes $p$ such that $-3$ is a quadratic residue modulo $p$. proof: This is a well known theorem (in fact, $-3$ can be replaced by any rational number), and this special version is very easy to prove using quadratic reciprocity law. But to keep the proof elementary, I present a elementary method here. Assume the contrary and assume $p_1,p_2,\dots,p_k$ are the only such odd primes ($k$ could be zero also!). Let $N = 2p_1p_2 \cdots p_k + 2$ and consider the number $T = N^2 + 3$. Note that $T \equiv 4 \pmod{p_i} ~ \forall ~ i \in \{1,2,\dots,k\}$ so this means that $T$ is not divisible by any of $p_1,p_2,\dots,p_k$. Also, $T$ is odd. This means there is a odd prime $p \notin \{p_1,p_2,\dots,p_k\}$ such that $p \mid T$. But then $-3$ is a quadratic residue modulo $p$, which is a contradiction. This proves the claim. $\square$ Corollary: There exist infinitely many primes $p$ such that $p \mid x^2 -x + 1$ for some $x \in \{1,2,\dots,p\}$. proof: Consider any odd prime $p \ne 3$ such that $-3$ is a quadratic residue modulo $p$ (by our claim, we know that there are infinitely many such $p$). Then there are two numbers $y$ in the set $\{1,2,\dots,p\}$ such that $p \mid y^2 + 3$. Note that at least one of these two numbers is odd (as the sum of these two numbers is equal to $p$, which is odd). In particular, there exist $x \in \{1,2,\dots,p\}$ such that $p \mid (2x-1)^2 + 3$. This implies $p \mid 4(x^2-x+1)$. As $\gcd(p,4)=1$, so this gives $p \mid x^2 - x + 1$, as desired. $\square$ We now return to the main problem. Consider any prime $p$ such that $p \mid x^2-x+1$ for $x = x_1,x_2 \in \{1,\ldots,p\}$ (by our corollary, we know that there are infinitely such $p$). We will prove that the graph $G_p$ has at most $p-2$ edges. Note all edges of $G_p$ are of the form $y \leftrightarrow y^2 + 1$. So at most $p$ edges. By conditions on $p$ at least two loops are also there. Done! $\blacksquare$

This works, right? Work entirely mod $p$. Define a directed graph $G'_p$ such that $m$ points to $n$ if and only if $n=m^2+1$; we allow $m=n$. It is clear that the outdegree of any vertex is $1$, so we have $p$ total edges. Now pick a prime $p$ dividing $m^2-m+1$ (of which there are infinitely many by Schur's Theorem) for some $m$, in which case $m \equiv m^2+1$, so $m$ points to itself. But note that since $m^2-m+1 \equiv 0 \pmod{p}$, we have $\tfrac{1}{m^2}-\tfrac{1}{m}+1 \equiv 0 \pmod{p}$ (by dividing by $m^2$), so $\tfrac{1}{m}$ points to itself. Since $m=1,-1$ obviously won't work for all but finitely many $p$, it follows that there are two different vertices connected to themselves, and therefore $p-2$ edges joining two distinct vertices. Since $m$ and $n$ (distinct) share an edge in $G_p$ only if $m \to n$ or $n \to m$ (possibly both) in $G_p'$, there are at most $p-2$ edges in $G_p$, but $p$ vertices, so $G_p$ must be disconnected. $\blacksquare$

Claim: For infinitely many primes $p\equiv 3\pmod{4}$ there exists an integer $k$ such that $p | k^4 - 3k^2 + 3$. Proof: Suppose $p_1$, $p_2$, ..., $p_n$ are the only such primes. Then $k = p_1p_2...p_n + 1$ leads to a contradiction. Now for any pair $(p,k)$ as in the claim, $k^2-1$ and $1-k^2$ form an entire connected component in $G_p$ so we are done.

best problem on shortlist better than a4 The idea is to count the total number of edges, which is counting the number of solutions to $m^2 + 1 - n \equiv 0\pmod p$. However, since for any $m$ there is exactly one unique working $n$, there are $p$ solutions total and thus at most $p$ edges total. Observe that if $m^2 + 1 \equiv n\pmod p$, then $(-m)^2 + 1 \equiv n\pmod p$ as well. Now, we do the dumbest thing possible; consider self edges, or $m^2 - m + 1 \equiv 0\pmod p$. By Schur's theorem infinitely many $p$ exist with solutions to the congruence. However, observe that $m^2 - m + 1 = (1 - m)^2 - (1 - m) + 1$, which means that both $m$ and $1 - m$ form self-loops unless $m \equiv 1 - m \pmod p$, or $m = \frac{p + 1}{2}$. We can check that \begin{align*} 4(m^2 - m + 1) = (2m - 1)^2 + 3 = p^2 + 3 \equiv 3\pmod p, \end{align*}so as long as we restrict $p > 3$ we know that $m$ is different from $1 - m$. This means we only have $p - 2$ edges to work with, and it's impossible to make a connected graph with $p - 2$ edges. Thus we are done.

Eyed wrote: For each prime $p$, construct a graph $G_p$ on $\{1,2,\ldots p\}$, where $m\neq n$ are adjacent if and only if $p$ divides $(m^{2} + 1-n)(n^{2} + 1-m)$. Prove that $G_p$ is disconnected for infinitely many $p$ We observe that for any fixed $m$, the equation $m^2 + 1 - n \equiv 0 \pmod{m}$ has a unique solution and therefore number of edges in $G_p$ is at most $p$. Now, due to Schur's Theorem, the polynomial $P(x) = x^2-x+1$ being non-constant polynomial has infinitely many primes $p$ dividing $P(x)$ for some positive integer $x$. In this case, we see that choosing any prime $p$ such that $p \mid P(x)$ for some $x\in \mathbb{Z}^+$, if we consider $y$ such that $y = 1-x \pmod{p}$, then $y^2 - y + 1 = (1-x)^2 - (1-x) + 1 = x^2 - 2x + 1 - 1 - x + 1 = x^2-x+1 \equiv 0 \pmod{p}$, therefore $G$ has two loops if $x \neq y$, which is $x \neq 1 - x \pmod{p} \implies x \neq \frac{p-1}{2} \pmod{p}$, but this reduces to $3 \equiv 4(x^2-x+1) \equiv 0 \pmod{p}$ so we restrict $p$ to be sufficiently large enough so that $G_p$ has two loops. However, loops are not considered as bridges, therefore number of edges in $G_p$ for such primes $p$ is $p-2$. However, $|E(G)| \geq p - c(G)$ with equality occuring at all connected components of $G$ being trees, therefore $p - 2 = |E(G)| \geq n - c(G) \implies c(G) \geq 2$, so $G$ is not a connected graph, as desired.

I claim that by choosing $p \equiv 7 \pmod{12}$ (there are infinitely many $p$ by Dirichlet), there exists a vertex with degree $0.$ Lemma: If a vertex $n$ satisfies $n^2 \equiv n-1 \pmod{p},$ it has degree $0.$ This implies for all $m\neq n,$ $n^2+1-m \not\equiv 0 \pmod{p}.$ Also, $n-1 \equiv n^2 \not\equiv m^2 \pmod{p},$ so neither conditions are satisified. Now, $$n^2 \equiv n-1 \pmod{p}$$$$\Leftrightarrow (2n-1)^2 \equiv -3 \pmod{p},$$so it suffices to show the existance of an $n,$ or $\left(\frac{-3}{p}\right) = 1,$ $$\Leftrightarrow \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} (-1)^{\left \lfloor{\frac{p+1}{6}}\right \rfloor} = 1,$$and checking $p \equiv 7 \pmod{12}$ easily verifies the above. The conclusion follows $\blacksquare$

For $p\neq 3$ we will work towards a formula for the number of pairs $(m,n)$, $m<n$, such that $p$ divides $(m^2 - n + 1)(n^2 - m + 1)$. (One does not need a complete formula to solve the problem, as using $B\geq 0$ below is enough - so let's display the formula only as additional content at the end.) Regarding $n \equiv m^2 + 1 \pmod p$, note that each $m$ gives a unique $n$ so this congruence has exactly $p$ solutions. Similarly, $m \equiv n^2 + 1 \pmod p$ also has $p$ solutions. It remains to subtract the pairs $(m,n)$ which simultaneously satisfy $n \equiv m^2 + 1$ and $m \equiv n^2 + 1$. As $n-m \equiv m^2 -n^2$ if and only if $(m-n)(m+n+1) \equiv 0$, these pairs either have to be with $m=n$ and $p \mid n^2 - n + 1$ (let their number be $A$) or with $m\equiv -n-1 \pmod p$ and $p \mid n^2 + n + 2$ (let their number be $B$). We have $A=0$ if $p\equiv 2 \pmod 3$ (many ways to prove: e.g. consider $n^3 \equiv -1$, raise with power $\frac{p+1}{3}$ and apply Fermat's little theorem; or rewrite as $(2n-1)^2 + 3 \equiv 0 \pmod p$ and use when is $(-3)$ a quadratic residue) and $A=2$ if $p\equiv 1 \pmod 3$ (use $(2n-1)^2 + 3 \equiv 0 \pmod p$ and when is $(-3)$ a quadratic residue; note that if $n$ was unique then we would have had $2(2n-1) \equiv 0$ and hence $p\mid 3$, contradiction for $p\neq 3$). Regarding $B$, having $B\geq 0$ is enough for this problem. The total number of ordered pairs $(m,n)$, without taking $m<n$ into account, is hence $2p - A - B$. So taking into account $m=n$ and that $(m,n)$ is a solution if and only if $(n,m)$ is, the number of pairs with $m<n$ is $\frac{2p-A-B-A}{2} = p - A - \frac{B}{2} = p - 2 \cdot 1_{p\equiv 1 \pmod 3} - \frac{B}{2} \leq p - 2 \cdot 1_{p\equiv 1 \pmod 3}$. To finish off, note that every connected graph on $p$ vertices must have at least $p-1$ edges - thus for $p\equiv 1 \pmod 3$ connectedness is impossible. As there are infinitely many primes of this form, we are done. Remark. To understand the value of $B$, let also $p\neq 2, 7$ and note that $p\mid n^2 + n + 2$ if and only if $(2n+1)^2 + 7 \equiv 0 \pmod p$. We cannot have $B=1$ since then $2(2n+1) \equiv 0 \pmod p$ and so $p\mid 7$, contradicting $p\neq 7$. Now, $B=2$ if and only if $(-7)$ is a quadratic residue modulo $p$ - but $\left(\frac{-7}{p}\right) = (-1)^{\frac{p-1}{2}}\left(\frac{7}{p}\right) = -\left(\frac{p}{7}\right)$ is $1$ if and only if $p\equiv 3,5,6 \pmod 7$. Therefore the total number of pairs for $p\neq 2, 3, 7$ is $$ p - 2 \cdot 1_{p\equiv 1 \pmod 3} - 1_{p\equiv 3,5,6 \pmod 7}. $$

LEMMA A graph on $n$ vertices and $n-2$ edges or fewer is disconnected. PROOF We will prove this by induction on $n$. The base case is $n=2$. This is obvious because there is only 1 graph on $2$ vertices and $0$ edges and it is disconnected. Let $G$ be a graph on $n$ vertices and $n-2$ or fewer edges. If any vertex of $G$ has no edge, then $G$ is disconnected. So, assume every vertex of $G$ has at least one edge. By the Pigeon-Hole principle, there exists some vertex $v$ with exactly one edge. (If every vertex had $2$ or more edges, there would have to be at least $n$ edges.) Let $H$ be $G$ but without $v$. Because there is an edge connected to $v$, $H$ has one fewer edge than $G$. So, the number of edges of $H$ is less than or equal to $n-3$. Because $H$ has $n-1$ vertices, by the inductive hypothesis, $H$ is disconnected. So, let $w$ and $x$ be two vertices of $H$ with no path between them. Assume towards a contradiction that there is a path between $w$ and $x$ in $G$. Then, because there is no path between them in $H$, the path must pass through $v$. However, $v$ only has one edge, so this is impossible. Therefore, $G$ is disconnected. LEMMA There are infinitely many prime numbers $p$ such that $-3$ is a quadratic residue $\mod{p}$. PROOF Assume towards a contradiction that a finite set $S$ contains every prime number $p$ besides 3 such that $-3$ is a quadratic residue $\mod{p}$. Let $P$ be the product of every element of $S$. Because $3\not \in S$ and $P^2+3\equiv 3\pmod{p}$ for every $p\in S$, $$P^2+3\not \equiv 0\pmod{p}$$for every $p\in S$. Let $q$ be a prime such that $q|P^2+3$. Because $$P^2+3\equiv 0\pmod{q},$$$q\not\in S$. In addition, because $P^2+3$ is not a multiple of $3$, $q\neq 3$. However, $-3$ is a quadratic residue $\mod{q}$, a contradiction. CLAIM There exist infinitely many $p$ such that $G_p$ is disconnected. PROOF Let $p$ be a prime such that $p\neq 2, 3$ and let $-3$ be a quadratic residue mod $p$. By the second lemma, there are infinitely many such values of $p$. Let $k^2\equiv -3\pmod{p}$. Let $n\equiv 2^{-1}(1+k) \pmod{p}$ and $m\equiv 2^{-1}(1-k)\pmod{p}$. Then, $$n^2+1\equiv (2^{-1}(1+k))^2+1\equiv 2^{-2}(1+k^2+2k)+1\equiv 2^{-2}(-2+2k)+1\equiv 2^{-1}(-1+k)+1\equiv 2^{-1}(1+k)\equiv n$$Similarly, $$m^2+1\equiv (2^{-1}(1-k))^2+1\equiv 2^{-2}(1+k^2-2k)+1\equiv 2^{-2}(-2-2k)+1\equiv 2^{-1}(-1-k)+1\equiv 2^{-1}(1-k)\equiv m$$Assume towards a contradiction $n\equiv m\pmod{p}$. Then, $$2^{-1}(1+k)\equiv 2^{-1}(1-k)\pmod{p}$$$$1+k\equiv 1-k\pmod{p}$$$$2k\equiv 0\pmod{p}$$$$4k^2\equiv 0\pmod{p}$$$$-12\equiv 0\pmod{p}$$$$p|12$$However, we are assuming $p\neq 2, 3$, a contradiction. We claim $G_p$ has at most $p-2$ edges. Let $x$ and $y$ be adjacent. $$p|(x^2+1-y)(y^2+1-x)$$By the definition of prime, either $$p|(x^2+1-y)$$or $$p|(y^2+1-x).$$So, $$x^2+1\equiv y\pmod{p}$$or $$y^2+1\equiv x\pmod{p}$$ Clearly, for every $y$, there is only one $0<x\leq p$ such that $y^2+1\equiv x\pmod{p}$. Every edge is of this form. Let $G'$ be a directed graph such that each edge points from $x$ to the residue of $x^2+1\pmod{p}$. So, $G'$ will have all of the edges of $G_p$. Each vertex has at most one edge pointing out of it. If $x^2+1\equiv x\pmod{p}$, then there is no edge pointing out of $x$. Because $m^2+1\equiv m\pmod{p}$ and $n^2+1\equiv n\pmod{p}$ and $n\not\equiv m\pmod{p}$, there are at least two vertices with no edge pointing outwards. So, there are at most $p-2$ edges. By the first lemma, $G'$ is not connected, so $G_p$ is not connected. Therefore, there are infinitely many values of $p$ such that $G_p$ is not connected.

Since $p$ prime we are only drawing down edges $(m,m^2+1).$ If we draw this edge for every $m$, and we allow double edges are loops, if there are two double edges or loops we are done. Loops happen when $p\mid m^2-m+1$ which is when $m^3\equiv -1 \pmod p$ but $m\not\equiv -1\pmod p$. It remains to show that there are infinitely many $p$ such that $p\mid m^3+1$ for at least three values of $p.$ Consider primes of the form $3k+1.$ Now, note that if $m=-n$ then $n^3\equiv 1\pmod p.$ This is a lot easier to work with and there is a bijection mapping between $m$ and $n.$ We have $r^{3k}\equiv 1\pmod p$ for any $r$ so if we let $n=1^k,2^k,\dots,(p-1)^k.$ To show that there are at least three distinct values amongst these: take a nonzero value $t^k\not\equiv 1\pmod p$ and take $t^k,\left(t^k\right)^2,\left(t^k\right)^3.$ Since there are infinitely many primes $3k+1$ we're done.

Construct a new directed graph where we draw an edge from $m\to n$ if $n\equiv m^2+1\pmod p$. Then note that this is a functional graph and the number of components in the undirected version is equal to the number of cycles in the functional graph. The undirected version is simply $G_p$ so it suffices to show that for infinitely many $p$ we have at least two cycles in the undirected version. We must have $$x^2-x+1\equiv y^2-y+1\equiv 0\pmod p$$for some $x\neq y$ which implies that $x+y\equiv 1\pmod p$ and $2x\not \equiv 1\pmod p$. Suppose that $p=2k-1$ and $x\equiv k\pmod p$. Then $2k-1\mid k^2-k+1$ and so $2k-1\mid k^2+k$ which means that either $2k-1\mid k$ or $2k-1\mid k+1$, neither of which are true for sufficiently large $p$. Then it suffices to show that there exist arbitrarily large $p$ that divide $x^2-x+1$, which follows from Schur's Theorem. $\blacksquare$

The pairs $(m,n)$ that are connected satisfy $p \mid (m^2+1-n)$ or $p \mid n^2+1-m,$ ie. $m^2 \equiv n-1 \pmod{p}$ or $n^2 \equiv m-1 \pmod{p}.$ Thus, the edge set is formed by connecting the quadratic residues $\{0^2,1^2,\ldots, \left( \frac{p+1}{2} \right)^2 \},$ with $k^2+1$ connected to $k$ and $-k.$ Thus, if we consider $k$ such that $k^2+1 \equiv k \pmod{p}$ and $\left( \frac{-k-1}{p} \right) = -1$ or $\left( \frac{k+1}{p} \right) = 1$ then the graph is disconnected because $k$ is only connected to $-k,$ and $-k$ is only connected to $k.$ Work in $\mathbb{F}_p.$ Then $k^2-k+1 = 0.$ So $k = \frac{1 \pm \sqrt{-3}}{2}$ which exists iff $\left( \frac{-3}{p} \right) = 1.$ And we also want $\left( \frac{ 2^{-1} (3 + \sqrt{-3}) }{p} \right) = 1$ Then it suffices to find an integer polynomial with roots in $\sqrt{ \frac{3 \pm \sqrt{-3}}{2} },$ but we see that $k^4-3k^2+3 = 0 \pmod{p}$ has these as solutions. But note that if $k^4 - 3k^2 + 3 = 0$ has solutions then $x = k^2$ satisfies $x^2 - 3x^2 + 3 = 0$ also has solutions, ie. of the form $x = \frac{3 \pm \sqrt{-3}}{2}.$ It follows that if $k^4-3k^2+3$ has solutions then $\left( \frac{-3}{p} \right) = 1.$ Thus, existence of solution to $k^4 - 3k^2 + 3 = 0 \pmod{p}$ is sufficient to guarantee both conditions hold. It is well known that for any nonconstant integer polynomial $f(x)$ with nonzero constant term there are infinitely many primes $p$ such that $p \mid f(n)$ for $n \in \mathbb{Z}.$ The result follows. $\blacksquare$

We claim that $G_p$ is disconnected when $p\equiv 7\pmod{12}$ and dirichlet ensure that there are infinitely many such $p$. Construct a digraph $G'_p$ with same vertices as $G_p$ and same edge but we add the arrow such that $a\to b $ if and only if $a^2+1\equiv b\pmod{p}$. This means that for any two distinct vertices $m,n$ in $G_p$, $m$ and $n$ are adjacent if and only if in $G_p'$, we have $m\to n$ or $n\to m$ Motivated by the fact that we want $m\to n$ as least as possible so that the graph is disconnected, we consider when $x^2+1\equiv x\pmod{p}$. $$x^2+1\equiv x\pmod{p}\iff (2x-1)^2\equiv -3\pmod{p}$$By quadratic residue computation, we get that $\left(\frac{-3}{p}\right)=1$ so there is such $x$. Obviously there are two solutions, let them be $a,b$. By definition, we have that the only vertex $a$ point to is $a$ itself which is impossible. We get the same for $b$. Now, let us consider which vertex point to $a$. $$x^2+1\equiv a\pmod{p}\iff x^2+1\equiv a^2+1\pmod{p}\iff x\equiv a,-a\pmod{p}$$Thus, the only vertex point to $a$ is $p-a$ and the only vertex point to $b$ is $p-b$. Obviously the only vertex $p-a$ point to is $a$ and the only vertex $p-b$ point to is $b$. We claim that either $p-a$ or $p-b$ has no vertex pointing to it. If it is true, we get that $\{a,p-a\}$ or $\{b,p-b\}$ is a connected component, so $G_p$ is disconnected. It's suffice to show that either $-a-1$ or $-b-1$ is NQR because then there will be no solution to $x^2+1\equiv -a\pmod{p}$ or $x^2+1\equiv -b\pmod{p}$. Note that \begin{align*} \left(\frac{(-a-1)(-b-1)}{p}\right)&=\left(\frac{ab+(a+b)+1}{p}\right) \\ &= \left(\frac{1+1+1}{p}\right) \\ &= \left(\frac{3}{p}\right) \\ &= -1 \end{align*}Hence, either $\left(\frac{-a-1}{p}\right)$ or $\left(\frac{{-b-1}}{p}\right)$ is NQR, as desired.

Call the prime $p$ good if it's a multiple of $x^2-x+1$ for some $x\in \mathbb{Z}^+.$ It's enough to show two following facts. Claim. There are infinitely many good primes. Proof. Assume not, so $p_1,p_2,...,p_n$ are all good primes. Then the contradiction with $\prod {p_i^2}-\prod {p_i}+1\equiv 0 \pmod {p_j}$. Claim. For all good $p>3$ graph $G_p$ is disconnected. Proof. Consider digraph $G_p'$ with vertices $1,2,...,p$, where directed edge $\overrightarrow{(m;n)}$ constructed in case $m\equiv n^2+1 \pmod p$ (loops are allowed). Clearly in every vertex enters exactly one edge, which is loop for some vertex $x\in [1;p-1].$ Since $$(p+1-x)^2-(p+1-x)+1\equiv x^2-x+1\pmod p,$$there is also a loop on vertex $p+1-x.$ Note that $x\neq p+1-x,$ since either $$0\equiv (p+1)^2-2(p+1)+4\equiv 3\pmod p,$$and therefore $G_p$ contains at most $p-2$ edges, which is less than in $p-\text{tree} ,$ thus the conclusion.

Here is my solution: https://calimath.org/pdf/ISL2020-N2.pdf And I uploaded the solution with motivation to: https://youtu.be/kiOFrq_-EOU

We claim this is the case for all $p\equiv 1\pmod 3$ (clearly infinitely many such $p$ by Dirichlets). Work in $\mathbb{F}_p$. Notice that all the edges are of the form $m\leftrightarrow m^2 + 1$ for all $m\in \{1,2,\ldots, p\}$ such that $m\not\equiv m^2 + 1\pmod p$. This implies there are at most $p$ edges. Claim: There exists a positive integer $x\le p$ such that $p\mid x^2 - x + 1$. Proof: Let $x \equiv g^{\frac{p-1}{6}}\pmod p$, where $g$ is a primitive root mod $p$. Notice that $p$ divides $x^6 - 1$ but not $x^2 - 1$ or $x^3 - 1$ (so $p$ also doesn't divide $x^2 + x + 1$). So $p$ divides \[\frac{x^6 - 1}{(x^2 - 1)(x^2 + x + 1)} = x^2 - x + 1,\]as desired. $\square$ Note that $x\equiv x^2 + 1 \pmod p$, which implies there is no edge connecting $x$ to $x^2 + 1$. We also have $\frac{1}{x}\equiv \left(\frac{1}{x}\right)^2 + 1 \pmod p$ (since $x\ne 0$), so there is also no edge connecting $1/x$ to $(1/x)^2 + 1$. Since $p>3$, we note that $x\ne -1,1$. This implies $G_p$ has at most $p-2$ edges, and thus is disconnected.

Here is my write up from some time ago. Cute problem. For brevity let us define $$S_p\overset{\mathrm{def}}{=}\{1, 2, \dots, p\}$$Take the obvious reformulation of the problem statement in the language of graph theory. Given a graph $G(E, V)$ with $p$ verticies $v_1, \dots, v_p$ we conect two vertices $u_n, u_m \in E(G)$ ($m\neq n$) if $p$ divides either $n^2-m+1$ or $m^2-n+1$. Prove that there are an infintely many primes $p$ such that $G$ is not conected. Claim: $\vert E(G)\vert \leq p$ Proof: We consider the directed (not necessarily simple) graph $\Gamma$ defined as follows. Each vertex $v_i$ represents the island numbered by $i$, $i\in S_p$. For $v_n, v_m\in V(\Gamma)$ we have a directed edge $\overrightarrow{v_nv_m}\in E(\Gamma)$ if and only if $p\vert n^2-m+1$ It is not hard to see that $\vert E(G)\vert \leq \vert E(\Gamma)\vert$, since if $u_nu_m\in E(G)$ is an edge in $G$, then either $$p\vert n^2-m+1 \text{ or } p\vert m^2-n+1$$and hence one of the edges $\overrightarrow{v_nv_m}$ or $\overrightarrow{v_mv_n}$ must be in $E(\Gamma)$. We have an inequality to account for the fact that $n$ and $m$ may be equal. Notice that, one we fix $n$, the congruence $n^2-m+1\equiv 0 \pmod p$ has exactly one solution for $m\in S_p$. Thus every vertex has exactly one directed edge leaving $v_n$. Since we can do this for every $n\in S_p$, then $\vert E(\Gamma)\vert=p$, and the claim is proven. $\blacksquare$ Now, we now that a graph with $n$ verticies must have at least $n-1$ edges for it to be connected. In particular, if we can find infinetly many primes $p$ such that $\vert E(G)\vert =p-2$ we would be done. This can only happen if the equation $$x^2-x+1\equiv 0 \pmod p\Longleftrightarrow (2x-1)^2\equiv -3 \pmod p$$has two solutions modulo $p$, since in that case two distinct verticies in $V(\Gamma)$ would be connected to themselves, $p-2$ edges in $G$. Since if we have one solution we immediatly have another, it suffices for $-3$ to be a quadratic residue modulo $p$. We calculate $$1=\left(\dfrac{-3}{p}\right)=\left(\dfrac{-1}{p}\right)\cdot \left(\dfrac{3}{p}\right)=(-1)^{\frac{p-1}{2}}\cdot \left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)\Longleftrightarrow p\equiv 1 \pmod 3$$Since there are an infinetly many primes of the form $3k+1$ (by Dirichlet, say) we are done! $\square$

Here is a motivated solution By the problem condition if $m^2+1\equiv n \pmod{p}$ or $n^2+1\equiv m \pmod{p}$ then $m$ and $n$ are connected This is equivalent to just saying $m$ and $m^2+1$ are connected for $m=1,2,...,p$ (we take $m^2+1$ mod $p$ and if it is $0$ we write $p$) Hence the number of edges in $G_p$ is at most $p$ This is a very small number so this motivates taking some $p$ such that some of these edges overlap or are self edges If the number of edges in $G_p$ were $p-2$ then it would definitely be disconnected So we will try to get rid of $2$ edges from this graph Since it's easier, we will try to find $p$ such that $m$ and $m^2+1$ is a self edge This means we want to have a solution to the congruence $m^2+1\equiv m\pmod{p}$ $m^2-m+1\equiv 0\pmod{p}$ $m^2-(p+1)m+1\equiv 0\pmod{p}$ $m^2-2\cdot \frac{p+1}{2}m+(\frac{p+1}{2})^2+1-(\frac{p+1}{2})^2\equiv 0\pmod{p}$ $(m-\frac{p+1}{2})^2\equiv (\frac{p+1}{2})^2-1\pmod{p}$ $(m-\frac{p+1}{2})^2\equiv \frac{(p-1)(p+3)}{4}\pmod{p}$ $(2m-(p+1))^2\equiv (p-1)(p+3)\pmod{p}$ $(2m-1)^2\equiv -3\pmod{p}$ So we have $1=(\frac{-3}{p})=(\frac{-1}{p})(\frac{3}{p})=(-1)^{\frac{p-1}{2}}\cdot (-1)^{\frac{3-1}{2} \frac{p-1}{2}}\cdot (\frac{p}{3})=(\frac{p}{3})$ So take $p\equiv 1\pmod{3}$, here we have a solution for the congruence $m^2+1\equiv m\pmod{p}$ Even more, if $x_1$ is a solution to $x^2\equiv -3\pmod{p}$ then so is $x_2\equiv -x_1\pmod{p}$ Hence we have $2$ solutions to the equation $m^2+1\equiv m\pmod{p}$ This means that at least $2$ of the edges are self edges (there are exactly $2$ but this isn't important) which means there are at most $p-2$ real edges Just as we mentioned this solves the problem since there are infinitely many primes $p\equiv 1\pmod{3}$ by Dirichlet's theorem

We define the following directed version of $G_p$: let $S$ be the directed graph on $\mathbb{F}_p$ where we place an edge $m \to n$ iff $n\equiv m^2+1 \pmod{p}$. First, we examine the self loops in this graph. Note that there is a self loop at $x$ iff \[ x \equiv x^2+1 \pmod{p} \iff x^3 \equiv -1 \pmod{p} \ \text{and} \ x \not\equiv -1 \pmod{p} \iff \text{ord}_p(x)=6. \]Thus, for $p \equiv 1 \pmod{6}$, we can pick a primitive root $g$ modulo $p$, and according to the above logic there are self loops at $g^{\frac{p-1}{6}}$ and $g^{-\frac{p-1}{6}}$. Hence, there are at least two self loops in this graph, provided $p \equiv 1 \pmod{6}$. Now, suppose that $p \equiv 1 \pmod{6}$. (We assume this for the remainder of the proof and use this for our construction, whence there are infinitely many such $p$ by Dirichlet's theorem.) Note that every vertex of $S$ has outdegree $1$, and that $S$ has at least $2$ self loops. Thus, undirecting $S$, $G_p$ has at most $p-2$ edges, but any connected graph on $p$ vertices has at least $p-1$ edges, so $G_p$ is disconnected, as desired.

We will simply prove that if $p\equiv 1\pmod{12}$, then $G_p$ is disconnected. This will finish by Dirichlet's. Lemma 1. There exists two positive integers $k\le p$ such that $k^2+1\equiv k\pmod p$. Proof. By Quadratic Reciprocity, $-3$ is a QR mod $p$. $k=\frac12(\pm\sqrt{-3}+1)$ suffice. Let $G'$ be the (not necessarily simple) directed graph on the same vertices as $G_p$ such that $m\rightarrow n$ iff $m^2+1\equiv n\pmod p$. Then obviously $G'$ has $p$ edges. However, by lemma 1, there are at least two edges that go from a node to itself. Therefore, since the edges of $G_p$ is a subset of the edges of $G$, $G_p$ has at most $p-2$ edges and thus must be disconnected. $\blacksquare$

basically equivalent to other solutions in this thread this is my favorite problem ive ever done and idk why Take $p \equiv 7 \pmod{12}$, of which there exists infinitely many by Dirichlet. Make a new graph that is directed (and not necessarily simple), with $m \rightarrow n$ iff $n\equiv m^2+1 \pmod{p}$. Note that there exist integers such that $x^2 - x + 1 \equiv 0 \pmod{p}$; let these integers be $a$ and $b$. Also note that only $-a$ points to $a$ and similarly for $b$. If we show that there are no solutions to $x^2 + 1 \equiv -a \pmod{p}$ or $x^2 + 1 \equiv -b$, then we are done since this implies no element of our new graph points to $-a$ or $-b$, so $a, -a$ will be isolated from all other vertices. But this is equivalent to showing that at least of $-1-a, -1-b$ is a NQR, which is true since \[ \left(\frac{-1-a}{p}\right)\left(\frac{-1-b}{p}\right) = \left( \frac {(-1-a)(-1-b)}{p}\right)= \left( \frac 3p \right) = -1\]which implies one of $\left(\frac{-1-a}{p}\right)$, $\left(\frac{-1-b}{p}\right)$ equals $-1$ as desired.

It remains to show that the arrow graph $n \mapsto n^2 + 1$ has more than one cycle infinitely many times. Take $p \mid P(x) = n^2 - n + 1$ for some $n \not\equiv -1 \pmod{p}$ and $p > 3$. By factoring $P$ over ${\mathbb F}_p$, it follows that there must be another distinct root of $P$. By Schur's lemma, we get infinitely many such $p$, finishing.

Let $p\equiv 1 \pmod 3$ be a prime. Note that $G_p$ has at most $p$ edges; specifically, we can construct $G$ by connecting $i$ to $i^2+1$ for $i=1,2\dots,p$. Now, if $n=g^{\frac{p-1}{3}}$ for a primitive root $g$, the edge going out from $n$ is ``wasted'' since it loops back to itself. Similarly, the edge going from $n^2$ is wasted, so delete it and the edge from $n$ since they dont affect whether the graph is connected. What remains is a graph on $p$ vertices with at most $p-2$ edges, finishing.

Assume $p\geq 7$. We claim that if $-3$ is a quadratic residue mod $p$, then there are at most $n-2$ edges in the graph, which would make it disconnected. Orient the edges so that $a\rightarrow b$ when $b\equiv a^2+1\pmod{p}$. Each vertex clearly has outdegree at most 1. However, if $a$ satisfies $$a\equiv a^2+1\pmod{p},$$then the outdegree of $a$ is zero, since the edge cannot go to itself. Completing the square gives $$(2a-1)^2\equiv -3\pmod{p}.$$Thus, if $-3$ is a QR mod $p$, then we will get two solutions for $a$, causing two vertices to have outdegree 0 and thus at most $n-2$ edges. Note that $3$ is a QR when $p\equiv 1,11\pmod{12}$. Thus, when $p\equiv 1\pmod{12}$, $3$ and $-1$ are both QRs, so $-3$ is a QR. Thus all $p\equiv 1\pmod{12}$ work and we are done. remark- the motivation is that each residue can only create at most one new edge, so there is very little "wiggle room" in terms of number of edges. When drawing small examples, $p=7$ and $p=13$ are disconnected, and it is evident that in both of these, there are too few edges, which strongly motivates trying an edge count related argument.

Construct a directed graph $G_p'$ on $\{1, 2, ..., p\}$ where $a$ is directed to $b$ iff $b \equiv a^2+1 \text{(mod p)}$. Any vertices direct to one vertex (might be itself). Then $G_p$ is just $G_p'$ with undirected edges and self-loop removed. In particular, since there are only $p$ edges on $G_p'$, two self-loops in $G_p'$ make $G_p$ disconnected. We have two self-loops precisely when there are two distinct $n$ modulo $p$ s.t. $$ n \equiv n^2+1 \iff n^2-n+1 \equiv 0 \iff (2n-1)^2 \equiv -3 \text{ (mod $p$)}.$$Note if there are repeated roots of $x^2+3 \equiv 0$, it is implied that $x \equiv -x$ and thus $x \equiv 0$, a contradiction if $p>3$. It's left to choose infinite $p$ that $-3$ is quadratic residue modulo $p$. Indeed, by picking $p = 3k+1$, $$ (\frac{-3}{p}) = (\frac{-1}{p})(\frac{3}{p}) = (\frac{-1}{p})(-1)^{\frac{p-1}{2}}(\frac{p}{3}) = (\frac{p}{3}) = 1, $$which exists infinitely many by Dirichlet.

Let $S=\{1,2,\ldots,p\}$. Consider the set $S'=\{a^2+1\ : \ a\in S\}$. Note that every edge in $G_p$ corresponds to one element from $S$ and the corresponding element from $S'$, given they are different. So, $e\leq |S|=p$ where $e$ is the number of edges in $G_p$. Note that if $e<p-1$, then the graph is disconnected. We show that this happens for infinitely many primes. If we show that there are two numbers for which the corresponding number in $S'$ is equal to the number is $S$, we are done. This is possible for infinitely many primes: Take $p\equiv1\pmod{6}$ and let $g$ be a primitive root $\pmod{p}$. Take $n\equiv g^{\frac{p-1}6}\pmod{p}$. Since $n^2-n+1$ is the sixth cyclotomic polynomial, we have $p\mid n^2-n+1$. Similarly we have for $n^5\pmod p$. Hence, $n,n^5$ correspond to themselves in $S'$. So, $e\leq p-2$ and we are done.

the problem clearly radiates the following emotion: xoink

Let us work in $\mathbb{F}_p$. Then $E(G_p)$ is precisely $\{\{n,n^2+1\}\mid n\in\mathbb{F}_p\}$ so $||G_p||\leq p$. We claim $p\equiv1\pmod3$ makes $G_p$ disconnected. Note that $x^3+1$ separates in $\mathbb{F}_p$ if $p\equiv 1\pmod3$. Thus $x^2-x+1$ separates in $\mathbb{F}_p$. The $2$ roots of $x^2-x+1$ form $2$ loops in $G_p$ so $||G_p||\leq p-2$ and thus $G_p$ is disconnected. By Dirichlet there are infinite such $p$. $\square$

this is not a number theory problem We instead consider the digraph $G$ generated by the function $f:\mathbb F_p \to \mathbb F_p$ where $f(n) = n^2+1$ (mod $p$). By taking $p \equiv 1 \pmod 3$, there are two roots to the equation $m^2 + 1 \equiv m \pmod p$, say $m_1$ and $m_2$. Then $m_1$ and $m_2$ form self-loops in $G$. But note that $G$ has precisely $p$ edges (every vertex has outdegree $1$), so there are $p-2$ edges that aren't self-loops. It follows that $G$ cannot be connected. Remark: By taking $p \equiv 7 \pmod {12}$ you can precisely characterize a connected component as $\{-m, m\}$ for such $m$. But why on earth would you ever do this? (Also, the edge counting argument isn't even needed because arrow graphs are disjoint cycles extended by trees...)

We claim that any $p$ for which $-3$ is a quadratic residue works. (There are infinitely many such primes due to quadratic reciprocity.) Firstly, we convert the graph $G_p$ into a directed graph; in particular, we point each edge so that $m$ points to $m^2 + 1$. Note that the outgoing edges of $\tfrac{1 - \sqrt{-3}}{2}$ and $\tfrac{1 + \sqrt{-3}}{2}$ both point to themselves, respectively. Suppose there exists some sequence of vertices $p_1, p_2, \dots, p_n$, connecting $\tfrac{1 - \sqrt{-3}}{2}$ and $\tfrac{1 + \sqrt{-3}}{2}$. Since each vertex has exactly one edge pointing out of it, $p_1$ must point left towards $\tfrac{1 - \sqrt{-3}}{2}$ and $p_n$ must point right towards $\tfrac{1 + \sqrt{-3}}{2}$. But this implies that there exists an $i$ such that $p_i$ points left and $p_n$ points right, which is a contradiction.

I claim that $p \equiv 1 \pmod 6$ implies $G_p$ is disconnected. We will show that $G_p$ has at most $p-2$ edges when $p \equiv 1 \pmod 6$, which is clearly enough (because of the existence of a spanning tree, a connected graph requires at least $p-1$ edges). Henceforth assume $p \equiv 1 \pmod 6$. Say that $m \rightarrow n$ if $m^2 + 1 \equiv n \pmod p$, and $1 \le m, n \le p$. Claim: There exist at least two $m$ with $m \rightarrow m$. Proof. Note that \[ m \rightarrow m \iff m^2 - m + 1 \equiv 0 \pmod p \]Now, pick a primitive root $g$ modulo $p$. Since $6 \mid p-1$, then we may consider $m \equiv g^{\frac{p-1}{6}} \pmod p$. Clearly, then \[ p \mid \frac{m^6-1}{(m^2+m+1)(m^2-1)} = m^2 - m + 1 \]which is true since $m$ has order $6$ modulo $p$. But notice that $m \equiv g^{5 \cdot \frac{p-1}{6}} \pmod p$ works as well, and they obviously cannot be equivalent. $\square$ This implies that there are at most $p-2$ pairs $(u, v)$ with $u \neq v$ and $u \rightarrow v$. Moreover, every pair $(u, v)$ with $u \rightarrow v$ can correspond to at most one connected edge in $G_p$, but every connected edge $(m, n)$ in $G_p$ must have $m \rightarrow n$ or $n \rightarrow m$. Hence there are at most $p-2$ edges in $G_p$, as needed. $\blacksquare$