# Visualizing quadratic residues and their structure

[I corrected the pictures and deleted one question due to user i707107’s valuable hint concerning cycles.]

Visualizing the functions $$μn mod m(k)=kn mod m\mu_{n\ \mathsf{ mod }\ m}(k) = kn\ \ \mathsf{ mod }\ \ m$$ as graphs reveals lots of facts of modular arithmetic, among others the fixed points of $$μn mod m\mu_{n\ \mathsf{ mod }\ m}$$ and the fact that $$μn mod m\mu_{n\ \mathsf{ mod }\ m}$$ acts as a permutation $$πnm\pi^n_m$$ of $$[m]={0,1,…,m−1}[m] = \{0,1,\dots,m-1\}$$ iff $$nn$$ and $$mm$$ are coprime. Furthermore the cycle structure and spectrum of $$πnm\pi^n_m$$ can be visualized and related to number theoretic facts about $$nn$$ and $$mm$$.

This is how the graph for $$μ3 mod 64(k)=3k mod 64\mu_{3\ \mathsf{ mod }\ 64}(k) = 3k\ \ \mathsf{ mod }\ \ 64$$ looks like when highlighting permutation cycles (the shorter the stronger):

When visualizing the function $$f2 mod m(k)=k2 mod mf^2_{\ \mathsf{ mod }\ m}(k) = k^2\ \ \mathsf{ mod }\ \ m$$ (which gives the quadratic residue of $$kk$$ modulo $$mm$$) in the same way as a graph, other observations can be made and tried to relate to facts of number theory, esp. modular arithmetic:

These graphs are not as symmetric and regular than the graphs for $$μn mod m\mu_{n\ \mathsf{ mod }\ m}$$ but observations can be made nevertheless:

• the image of $$f2 mod m{f^2_{\ \mathsf{ mod }\ m}}$$, i.e. those $$nn$$ with $$f2 mod m(k)=n{f^2_{\ \mathsf{ mod }\ m}}(k) = n$$ for some $$k (black dots)

• number and distribution of fixed points with $$f2 mod m(k)=k{f^2_{\ \mathsf{ mod }\ m}}(k) = k$$ (fat black dots)

• cycles with $$f2 mod m(n)(k)=k{f^2_{\ \mathsf{ mod }\ m}}^{(n)}(k) = k$$ (colored lines)

• parallel lines (not highlighted)

My questions are:

• How can the symmetric distribution of image points $$nn$$ (with $$f2 mod 61(k)=nf^2_{\ \mathsf{ mod }\ 61}(k)=n$$ for some $$kk$$, black dots in the picture below) be explained?

• Can there be more than one cycle of length greater than 1 for $$f2 mod mf^2_{\ \mathsf{ mod }\ m}$$?

• How does the length of the cycles depend on $$mm$$?

• How does the "parallel structure" depend on $$mm$$?

With "parallel structure" I mean the number and size of groups of parallel lines. For example, $$f2 mod 8f^2_{\ \mathsf{ mod }\ 8}$$ has two groups of two parallel lines, $$f2 mod 12f^2_{\ \mathsf{ mod }\ 12}$$ has two groups of three parallel lines. $$f2 mod 9f^2_{\ \mathsf{ mod }\ 9}$$ has no parallel lines.

For $$f2 mod 61f^2_{\ \mathsf{ mod }\ 61}$$ one finds at least four groups of at least two parallel lines:

For other prime numbers $$mm$$ one finds no parallel lines at all, esp. for all primes $$m≤11m\leq 11$$ (for larger ones it is hard to tell).

This is not a complete answer to all of your questions. This is to show you some things you need to investigate. The first question is answered. The second question has an example. I do not know complete answers to the third and fourth questions, but I give a try on explaining your plot of $$m=61m=61$$.

From your last sentences, it looks like you are interested in the case when $$mm$$ is a prime. Let $$m=pm=p$$ be an odd prime. Then consider $$p\equiv 1p\equiv 1$$ mod $$44$$, and $$p\equiv 3p\equiv 3$$ mod $$44$$.

In the former case $$p\equiv 1p\equiv 1$$ mod $$44$$, we see the symmetric black dots. This is because the Legendre symbol at $$-1-1$$ is $$11$$. That is
$$\left( \frac{-1}p \right)=1. \left( \frac{-1}p \right)=1.$$
This means $$-1-1$$ is a square of something in $$\mathbb{Z}/p\mathbb{Z}\mathbb{Z}/p\mathbb{Z}$$. Suppose $$x\equiv y^2x\equiv y^2$$ mod $$pp$$, then we have $$-x \equiv z^2-x \equiv z^2$$ mod $$pp$$ for some $$z\in\mathbb{Z}/p\mathbb{Z}z\in\mathbb{Z}/p\mathbb{Z}$$.

Your example $$m=61m=61$$ is a prime that is $$11$$ mod $$44$$. Thus, we have a symmetric black dots.

In general when $$pp$$ is an odd prime, the image of the square mapping is
$$\{ x^2 \ \mathrm{mod} \ p| 0\leq x \leq \frac{p-1}2 \}.\{ x^2 \ \mathrm{mod} \ p| 0\leq x \leq \frac{p-1}2 \}.$$
Note that the black dots represent image of the square mapping.

Thus, the number of black dots is $$\frac{p+1}2\frac{p+1}2$$. In your example of $$m=61m=61$$, we have $$3131$$ black dots.

Now we use a primitive root $$gg$$ in $$\mathbb{Z}/p\mathbb{Z}\mathbb{Z}/p\mathbb{Z}$$. Then any element $$x\in \mathbb{Z}/p\mathbb{Z} - \{0\}x\in \mathbb{Z}/p\mathbb{Z} - \{0\}$$, we have some integer $$aa$$ such that $$x\equiv g^ax\equiv g^a$$ mod $$pp$$. Then a cycle formed by square mapping which includes $$xx$$ can be written as
$$\{g^{a\cdot 2^k} \ \mathrm{mod} \ p| k=0, 1, 2, \ldots \}. \{g^{a\cdot 2^k} \ \mathrm{mod} \ p| k=0, 1, 2, \ldots \}.$$
To see if we have cycles, try solving
$$a\cdot 2^k \equiv a \ \mathrm{mod} \ p-1. a\cdot 2^k \equiv a \ \mathrm{mod} \ p-1.$$

In your plot of $$m=61m=61$$, we have a primitive root $$g=10g=10$$ and the following are cycles of length greater than $$11$$. All of these should be considered with modulo $$6161$$.
$$(g^{20} g^{40}), (g^{20} g^{40}),$$
$$(g^4 g^8 g^{16} g^{32}), (g^4 g^8 g^{16} g^{32}),$$
$$(g^{12} g^{24} g^{48} g^{36}), (g^{12} g^{24} g^{48} g^{36}),$$
$$(g^{56} g^{52} g^{44} g^{28}) (g^{56} g^{52} g^{44} g^{28})$$
I am not sure if you consider these as cycles, because there can be numbers in front of these, such as
$$g^5 \mapsto g^{10} \mapsto g^{20}, g^5 \mapsto g^{10} \mapsto g^{20},$$
and comes in to the cycle $$(g^{20} g^{40})(g^{20} g^{40})$$.