Jtdylktuy

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 $ncdot a equiv boperatorname{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$?

Note that $3^4=81equiv 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.

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

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

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

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

$qquadqquad 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\
&qquadqquadqquadquad equiv 60, 52, 28, 20
end{align}$

Note that in order to form a rectangle of the points ($p, ptimes q, ptimes 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$.