Let $p$ be a prime number. We construct a directed graph of $p$ vertices, labeled with integers from $0$ to $p-1$. There is an edge from vertex $x$ to vertex $y$ if and only if $x^2+1\equiv y \pmod{p}$. Let $f(p)$ denotes the length of the longest directed cycle in this graph. Prove that $f(p)$ can attain arbitrarily large values.
Problem
Source: SRMC 2023, P3
Tags: number theory, prime numbers, Quadratic Residues, Directed graphs, quadratics
R8kt
29.12.2023 02:19
Take P(x) = x^2+1 and let Q(n, i) be P(P(…P(i)…)) (P is applied n times). Them by size arguments for every n, there exist a prime dividing Q(n, 1) - 1, that doesn’t divide Q(m, 1) - 1 for all m<n. This prime gives a cyclic of length n. Done.
VicKmath7
29.12.2023 15:18
Basically the same solution but including the size arguments.
Let $P(x)=x^2+1$ and let $a_i=P^i(0)$ for all $i \geq 1$. Observe that $a_2>a_1$, so by induction, $a_{n+1}>a_n^2>a_1a_2 \ldots a_n$ for all positive integers $n \geq 2$. Fix a positive integer $n$; we will show that there exists a prime divisor $p$ of $a_n$, not dividing the previous $a_i$, which will imply that there is a cycle of length $n$ for that prime $p$. Indeed, there exists a prime $p$ such that $\nu_p(a_n)>\nu_p(a_1a_2 \ldots a_{n-1})$, so we will show it works. Suppose otherwise and let $p \mid P^{k}(0)$, where $k$ is minimal. Then $k \mid n$ and we will show that $\nu_p(a_{mk})=\nu_p(a_k)$ for all positive integers $m$, which will contradict the choice of $p$. Indeed, observe that the polynomial $P^{mk}(x)$ doesn't have a $x^1$ term, so we have $\nu_p(P^{(m+1)k}(0))=\nu_p(P^{mk}(a_k))=\min(\nu_p(P^{mk}(0)), 2\nu_p(a_k))$, so for $m=1$ it's $\nu_p(a_k)$, and for $m\geq 2$ by induction again it's the same, so we are done.