Explanation of an unexpected observation in modular arithmetic

Question

Let the multiplication graph $n:m$ be the graph with $m$ points equally distributed on a circle and a line between points $a$ and $b$ when $n\cdot a \equiv b\operatorname{mod} m$.

Looking at the multiplication graph $3:64$ with coprime $n, m$ reveals not so much at first sight – except of the ($n- 1$)-foil pattern that is to be expected for every "nominator" $n$:

But when highlighting permutation cycles – the shorter the stronger – something interesting appears:

What one sees are two $4$-cycles $(4,12,36,44)$ and $(20,60,52,28)$ which describe two perfect rectangles with integral side lengths $8 : 24 = 1 : 3$

I wonder which properties of $n$ and $m$ are responsible for the appearance of two such rectangles and their corresponding side lengths? Is it by sheer coincidence that $8$ is the square root of $64$?

Answer 1

Note that $3^4=81\equiv 17 \pmod {64}$ so multiplying a number by $3$ four times is equivalent to multiplying it by $17$. Now $4 \cdot 17 \equiv 4 \pmod {64}$ so multiplying any multiple of $4$ by $3$ four times will bring us back and we will have at most a $4-$cycle. The other cycle is just the negative of the first because $60 \equiv -4 \pmod {64}$. You have accounted for all the numbers that are equivalent to $4 \pmod 8$ in our system. The heavy lines in your figure connect the multiples of $8$ except $0,32$ in pairs because $3^2 \cdot 8 \equiv 8 \pmod {64}$ so multiplying a multiple of $8$ twice by $3$ will bring us back. Finally $0,32$ are the solutions to $3x \equiv x \pmod {64}$ so they are $1-$cycles.

Answer 2

Hint $ $ It's simply $\,3^{\large 4}\equiv 1\pmod{\!16}\,$ multiplied by $\,\color{#0a0}4,\,$ i.e.

$\qquad\qquad \begin{align} &\bmod 16\!:\ \ \ \ \ \ 3^n = \color{#c00}1,\ \ 3,\ \ 9,\,11,\, \color{#c00}1\ \ldots\\ \Rightarrow\ &\bmod 64\!:\ \color{#0a0}4\cdot 3^n = \color{#0a0}4,12,36,\,44,\ \color{#0a0}4\ \ldots \end{align}$

i.e. $\,\ 4\cdot 3^{\large k+4n}\!\bmod 64 = 4\,(3^{\large k}81^{\large n}\!\bmod 16) = 4\,(3^{\large k}1^{\large n}\!\bmod 16) = 4\cdot 3^{\large k}\bmod 64$

The second one is its negative, i.e. using $\,\color{#0a0}{{-}4}\,$ vs. $\,\color{#0a0}4\,$ i.e.

$\qquad\qquad \begin{align} &\bmod 16\!:\ \ \ \ \ \ \ \ \ 3^n = \ \ \ \color{#c00}1,\ \ \ \ \ 3,\ \ \ \ \ 9,\ \ \ \ 11,\ \ \ \ \color{#c00}1\ \ldots\\ \Rightarrow\ &\bmod 64\!:\, \color{#0a0}{{-}4}\cdot 3^n = \color{#0a0}{{-}4},-12,-36,\,-44,\ \color{#0a0}{{-}4}\ \ldots\\ &\qquad\qquad\qquad\quad\ \ \equiv\ 60,\ \ \ 52,\ \ \ 28,\ \ \ \ 20 \end{align}$

Answer 3

Note that in order to form a rectangle of the points ($p, p\times q, p\times q^2, p \times q^3$) to form a "rectangle" we need the following to occur. First, $p \times (q^2-1) \equiv \frac{m}{2} \mod m$, in order for the first and third elements to be diametrically opposite (and this the angle that forms that connects them (specifically at the $p \times q$ point) would be a right angle. Note this implies $m$ must be even, as there isn't a diametrically opposite point in an odd modulus. Note this must be true for the second and fourth elements as well, so $pq \times (q^2-1) \equiv \frac{m}{2} \mod m$. Finally, we need this to actually be a cycle of $4$, so $q^4 \equiv 1 \mod m$. From the first and second equations we essentially get that $q$ must be odd (in order for the multiplication of $q$ from the first to the second to not change the remainder mod $m$). Additionally, we need $m$'s totient function to either be $2$ or a multiple of $4$ in order for there to be solutions to the last question. Then, we can construct rectangles.

For an $m$, consider all the solutions to $q^4 \equiv 1 \mod m, q \neq 1$. Note $q$ must be odd. Now, note that $q^2-1 \equiv 0 \mod 4$, so the only way that this could be remainder of half a modulus is if the modulus is a divisor of 8. Assuming all of this is true, we now have $$2 * p \times (q^2-1) \equiv 0 \mod m,$$ now, we just find the solutions to this, and then ensure that $p \times (q^2-1) \equiv \frac{p}{2} \mod m $ and not $0 \mod m$, and then we have our solutions.

EDIT: To answer your second question, note that you are essentially asking to solve $$x \times (pq-p) \equiv (pq^2-pq) \mod m, $$ a solution to which is $q$.