# 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 $$\mu_{n\%m}(k) = kn\ \%\ m$$ (with $$a\ \%\ b$$ meaning $$a$$ modulo $$b$$) as graphs reveals lots of facts of modular arithmetic, among others the fixed points of $$\mu_{n\%m}$$ and the fact that $$\mu_{n\%m}$$ acts as a permutation $$\pi^n_m$$ of $$[m] = \{0,1,\dots,m-1\}$$ iff $$n$$ and $$m$$ are coprime. Furthermore the cycle structure and spectrum of $$\pi^n_m$$ can be visualized and related to number theoretic facts about $$n$$ and $$m$$.

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

When visualizing the function $$f^2_{\%m}(k) = k^2\ \%\ m$$ (which gives the quadratic residue of $$k$$ modulo $$m$$) 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 $$\mu_{n\%m}$$ but observations can be made nevertheless:

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

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

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

• parallel lines (not highlighted)

My questions are:

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

• Can there be more than one cycle of length greater than 1 for $$f^2_{\%m}$$?

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

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

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

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

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

• Use the CRT and the structure of $\mathbb{Z}/p^e\mathbb{Z}^\times$ to understand the multiplicative monoid of $\mathbb{Z}/m\mathbb{Z}$. You are supposed to start with the simplest case : $m$ odd prime, power of an odd prime, product of two primes (powers) – reuns Feb 14 at 6:11
• The parallelity has simple explanation. Obviously, the lines corresponding to $x\neq y$ are parallel if $x^2 + x = y^2 + y \pmod{m}$, which is equivalent to $x+y+1 = 0 \pmod{m}$. However, there can be no parallel lines visible if they collapse to a point (i.e $x^2 = x$) or coincide (when $x^2 = y, y^2 = x$). – zhoraster Feb 14 at 12:14
• E.g. for $m=5$, there is a suitable pair $(x,y) = (1,3)$, but $x^2 = x$, so no parallel lines. For $m=7$, there is a pair $(x,y) = (2,4)$, but $2^2 = 4$, $4^2 = 2$. For $m=11$, there are suitable pairs $(2,8)$, $(3,7)$, $(4,6)$, which are clearly visible. – zhoraster Feb 14 at 12:21
• By the way, for $m=9$, there are two pairs $(3,5)$ and $(2,6)$; why do you write there are none? – zhoraster Feb 14 at 12:40
• @zhoraster: Thanks for the hint. I've overseen them (having been "parallel blind") and removed the remark. – Hans-Peter Stricker Feb 14 at 12:58

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=61$$.

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

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

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

In general when $$p$$ is an odd prime, the image of the square mapping is $$\{ 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$$. In your example of $$m=61$$, we have $$31$$ black dots.

Now we use a primitive root $$g$$ in $$\mathbb{Z}/p\mathbb{Z}$$. Then any element $$x\in \mathbb{Z}/p\mathbb{Z} - \{0\}$$, we have some integer $$a$$ such that $$x\equiv g^a$$ mod $$p$$. Then a cycle formed by square mapping which includes $$x$$ can be written as $$\{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.$$

In your plot of $$m=61$$, we have a primitive root $$g=10$$ and the following are cycles of length greater than $$1$$. All of these should be considered with modulo $$61$$. $$(g^{20} g^{40}),$$ $$(g^4 g^8 g^{16} g^{32}),$$ $$(g^{12} g^{24} g^{48} g^{36}),$$ $$(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},$$ and comes in to the cycle $$(g^{20} g^{40})$$.

• Thanks a lot. Your considerations concerning cycles gave me an important hint: that I made a mistake in plotting the cycles - some of them got lost. I corrected the pictures and the corresponding questions in my post. – Hans-Peter Stricker Feb 14 at 11:57
• Maybe you want to have a look at this related question of mine: Puzzle (2): Explaining a pattern in quadratic residues graphs modulo $m$? – Hans-Peter Stricker Feb 14 at 14:25
• Good job. The numbers in front of a cycle come from killing the $2$-power torsion of the group $C_{p-1}$. The transition graphs are identical to those recently encountered here. – Jyrki Lahtonen Feb 15 at 3:41
• @JyrkiLahtonen: Thanks for the hint to Newton-Raphson graphs, which thrilled me: getting the same graphs by seemingly quite different approaches. (Or are the approaches essentially the same?) – Hans-Peter Stricker Feb 15 at 11:41
• @HansStricker My answer there is more or less about explaining that the transitions in Newton-Raphson are gotten from those of squaring by conjugating it with a Möbius transformation. Conjugation (by a bijection) produces isomorphic graphs of transitions. – Jyrki Lahtonen Feb 15 at 11:46