Pattern of Newton-Raphson iteration $x\mapsto\frac{1}{2}(x+\frac{q}{x})$ over finite fields While playing with Newton-Raphson method over finite field $\mathbb{F}_p$, I noticed some cute patterns that I can't explain out of my brain contaminated with analysis.
Here is the setting:

Setting. Let $p$ be an odd prime and $q \in \mathbb{F}_p$. Define the directed graph $G_{p,q}$ as follows:

*

*The vertex-set of $G_{p,q}$ is simply $\mathbb{F}_p$.

*A (directed) edge $[x, y\rangle$ is in the edge-set of $G_{p,q}$ if and only if $x^2 - 2xy + q = 0$ holds.

In the case $q \neq 0$, edges of $G_{p,q}$ are of the form $[x, f(x) \rangle$ for $f(x) = \frac{1}{2}(x+\frac{q}{x})$ and $x\in\mathbb{F}_p\setminus\{0\}$. Notice that $f$ is the exactly the function which arises in the Newton-Raphson's method for finding zeros of $x^2 - q$.

Here is a quick observation: For each $ y \in \mathbb{F}_p$, either

*

*$y^2-q$ is a non-zero quadratic residue modulo $p$, so that are exactly $2$ edges pointing at $y$.


*$y^2 - q = 0$ in $\mathbb{F}_p$, so that $\{y\}$ is a connected component of $G_{p,q}$ with the loop $[y, y\rangle$.


*$y^2 - q$ is not a quadratic residue modulo $p$, so that no edge points at $y$, i.e., $y$ is a leaf.
It seems that, for each given $p$, the connectivity structure of $G_{p,q}$ depends only on whether $q$ is a quadratic residue modulo $p$ or not. For instance, if $p=43$, then only the following two possibilities of connectivity emerge:

And the following is the case of $p=113$.

So the obvious question is

Question.
(1) Can we find an explanation as to why the connectivity structure of $G_{p,q}$ for $p$ odd prime and $q \in \mathbb{F}_{p}\setminus\{0\}$ seems to depend only on the quadratic residue of $q$?
(2) Can we relate any of the structure of $G_{p,q}$ in terms of number-theoretic properties of $(p, q)$? For instance, what is so special about this construction that components look so 'symmetric'?

I know that I am rather throwing random questions out of shallow curiosity, so forgive me if the questions look like not well-formed or it is already well-known. I would like to consider this question as a recreational one, and would appreciate any comment.
 A: Whenever $q_1, q_2$ are both quadratic residues modulo $p$, or both quadratic nonresidues modulo $p$, we can find a constant $c \ne 0$ such that $q_2 \equiv c^2 \cdot q_1 \pmod p$. Then multiplication by $c$ induces a graph isomorphism between $G_{p,q_1}$ and $G_{p,q_2}$:
$$
   (x,y) \in E(G_{p,q_1}) \iff x^2 - 2xy + q_1 \equiv 0 \\
 \iff (cx)^2 - 2(cx)(cy) + c^2q_1 \equiv 0 \iff (cx, cy) \in E(G_{p,q_2}).
$$
So in this case, $G_{p,q_1}$ and $G_{p,q_2}$ are going to look the same with only the vertices relabeled (and the relabeling is multiplication by $c$).
A: Assume first that $q$ is a quadratic residue modulo $p$.
By Misha Lavrov's answer we can then assume that $q=1$. We are interested in the behavior of the iterates of
$$
f(x):=\frac12\left(x+\frac1x\right).
$$
Consider the Möbius transformation from the set $P=\Bbb{F}_p\cup\{\infty\}$ to itself
$$
\mu(t):=\frac{t+1}{t-1}.
$$
We see that
$$
\begin{aligned}
f(\mu(t))&=\frac12\left(\frac{t+1}{t-1}+\frac{t-1}{t+1}\right)\\
&=\frac{t^2+1}{t^2-1}\\
&=\mu(t^2).
\end{aligned}
$$
This means that, up to conjugation by $\mu$, the mapping $f$ is just squaring in the set $P$. Therefore $f$ and squaring produce isomorphic graphs of transitions.
What happens in the set $P$ when we iteratedly square elements was studied in this thread (apologies for blowing my own trumpet to this extent). Anyway, we can say the following:

Assume $q$ is a quadratic residue. Write $p-1=2^m a,$ where $a$ is odd. Then
after $m$ iterations of $f$ the set of images has stabilized. Call this set $S$. Then further iterations will just permute the set $S$. The cycle structure of a single iteration on set $S$ can be gotten by looking at what happens with multiplication by two modulo $a$.

As an example let's consider the case $p=43$. This time $m=1, a=21$. Modulo $21$ multiplication by two produces the cycles
$$
(0)(1,2,4,8,16,11)(3,6,12)(5,10,20,19,17,13)(7,14)(9,18,15).
$$
Indeed, we see two 6-cycles, two 3-cycles and a single 2-cycle in Sangchul Lee's image of this graph.
On the other hand, with $p=113$ we get $p-1=2^4\cdot7$. This explains why we get the reverse of binary branching up to depth four, and then modulo $a=7$ we see the cycles
$$
(0)(124)(365).
$$

When $q$ is not a square of an element of $\Bbb{F}_p$ the situation is a little bit different. To apply the above ideas we also work inside the quadratic extension field $\Bbb{F}_p(\sqrt{q})$.
This time we are interested in the iterations of
$$
f(x)=\frac12\left(x+\frac q x\right).
$$
As above, we see that with (as observed by Sangchul Lee in a comment to the first part) the Möbius transformation
$$
\mu_q(t)=\sqrt q\frac{t+1}{t-1}
$$
we still get the squaring rule
$$
f(\mu_q(t))=\mu_q(t^2).
$$
A difference comes from selecting an appropriate set for the parameter $t$ to range over.
The question specifies that
$$
x=\mu_q(t)\qquad(*)
$$
should range over $x\in\Bbb{F}_p$. Solving for $t$ from the equation $(*)$ gives
$$
t=\frac{x+\sqrt{q}}{x-\sqrt{q}}.
$$
Lemma. When $x$ ranges over $\Bbb{F}_p\cup\{\infty\}$ the fraction
$t=(x+\sqrt q)/(x-\sqrt q)$ ranges over the multiplicative group of norm
one elements of $\Bbb{F}_{p^2}$. In other words,
$$
S:=\left\{\frac{x+\sqrt{q}}{x-\sqrt{q}}\bigg\vert\,x\in\Bbb{F}_p\cup\{\infty\}\right\}
=\{z\in\Bbb{F}_{p^2}\mid z^{p+1}=1\}.
$$
Proof.
The non-trivial automorphism of the field $\Bbb{F}_{p^2}$ is clearly
$$F:a+b\sqrt q\mapsto a-b\sqrt q.$$
On the other hand, by the well known Galois theory of finite fields, $F$ must be the Frobenius automorphism and we also have $F(z)=z^p$. In particular, $(x\pm\sqrt q)^p=x\mp\sqrt q$ for all $x\in\Bbb{F}_p$. Therefore, if $z=(x+\sqrt q)/(x-\sqrt q)$ we have
$$
z^p=F(z)=\frac{x-\sqrt q}{x+\sqrt q}=\frac 1z.
$$
This implies that $z^{p+1}=1$. Because the multiplicative group $\Bbb{F}_{p^2}^*$ is cyclic of order $p^2-1=(p-1)(p+1)$, the equation $z^{p+1}=1$ has $p+1$ solutions in $\Bbb{F}_{p^2}$. Different choices of $x$
lead to different values for $z$, so we have found all those solutions. QED.
The rest is then easy. We know that $S$ is a cyclic group of order $p+1$.
Repeating the earlier argument we arrive at the following description:

Assume that $q$ is a quadratic non-residue. Write $p+1=2^\ell b$, $b$ odd.
Then after $\ell$ iterations the image of $f$ has stabilized. Any further iterations of $f$ will permute this set with the same cycle structure as
multiplication by $2$ permutes the residue classes modulo $b$.

As an example consider the case $p=43$, $q=3$ from the top right image in Sangchul Lee's question. Here $p+1=44=2^2\cdot11$. Therefore the graph has two stages of binary branch convergence. Modulo $b=11$ multiplication by two looks
like
$$(0)(1,2,4,8,5,10,9,7,3,6)$$
explaining the emergence of a 10-cycle (and a fixed point) seen in the image.
Similarly, when $p=113$, we get $p+1=114=2\cdot57$. After a single step of two branches converging we are left to study the cycles of multiplication by two modulo $57=3\cdot19$. Two is a primitive root modulo $19$, so it follows that
we get three 18-cycles, a fixed point $0$, and a 2-cycle $(19,38)$. Again, in accordance with the graph in the bottom right.

Remark: I cooked up an analogue of the Lemma once to study certain character sums. A colleague used it to study correlation properties of certain families of sequences.
See this MathOverflow thread, where Michael Zieve does something similar. Also see Peter Mueller's answer for a generalization. So I am not the inventor. I simply had not seen it before. Anyway, the Lemma is totally analogous to the fact that
$$
\left\{\frac{x+i}{x-i}\in\Bbb{C}\bigg\vert\,x\in\Bbb{R}\cup\{\infty\}\right\}
$$
is the unit circle of the complex plane.
