Why is $n_{n^2-1}$ the smallest graph that clearly shows the structure of multiplication by $n$?

Question

Initially, I wanted to ask this question as a puzzle.

1. Consider a regular $m$-gon. Let $0$ be the lower corner and count the corners clockwise.

2. Let $n_m$ be the multiplication-by-$n$-graph of $m$ for $n < m$ by drawing an arrow from every corner $a$ to the corner $a\cdot n\operatorname{mod}m$.
   _{These are the eight relevant multiplication-by-$n$-graphs of $10$ as (hopefully) intelligible to every school kid:}

3. For fixed $n$, in the limit $m \rightarrow \infty$ the graph $n_m$ will somehow display $n-1$ cusps.
   _{E.g. $10_{517}$:}
   

4. What is the smallest graph $n_m$ that undeniably displays $n-1$ cusps?

You may think hard about this (or not), but the (probably right) answer can be found easily by simulation: Just draw the graphs

and you will find that the graph with $m = n^2-1$

yields this smallest graph.

Be promised: It's the same for arbitrary $n$ instead of $10$:

Even for smaller $n$ than $10$:

My question is:

Why is this so?

I'm looking for strong algebraic and/or arithmetic arguments. I have no idea.

Answer 1

At the request of Gerry Myerson, here is what I understand.

As $n^2=1$ modulo $n^2-1$, the multiplication by $n$ graph on $m=n^2-1$ vertices as defined in the question is formed

1) First, of isolated points which satisfy $nx=x$, or equivalently $(n+1)|x$, of which there are $n-1$. These are the $n-1$ initial point of each "cusps" (a "cusp" is a group of $n+1$ consecutive points on the circle starting with a point congruent to 0 modulo $n+1$).

2) Second, of bi-directional edges relating a pair of points. Now, if $x=y+k(n+1)$ with $0\leq y\leq n$, then $nx=ny+k+kn=ny+k(n+1)=-y+(k+y)(n+1)$ so each point in the $n+1$ terms are linked to a different group.

This entirely explains the nice display when $m=n^2-1$. If $m<n^2-1$, then $(n-1)(n+1)>m$, so there can be no periodicity of the form above.

Now, how about the assertion that when $m$ is large with respect to $n$, we do see $n-1$ "cusps"? The slopes of two consecutive edges (corresponding to $nx$ and $n(x+1)$) are increasing. Visually, if you incrementally increase slopes of lines, this draws the convex envelope of a cusp (people who know more than me about geometry, that is to say people who know anything at all, will tell us the equation of the cusp drawn in this way). Whence the cusps. When will the cusps be dark (almost vertical slope)? When the edges are close to diameters. And when will that be? When $nx$ is close to $x+m/2$. If that is the case, then $n(x+m/(n-1))$ will also be close to $x+m/(n-1)+m/2$. So we see $n-1$ maximally dark cusps (and likewise one can count the relatively darker cusps by cutting the circle in 3, 4 etc. and translate in terms of congruences).

Putting everything together, if $m$ is large, we see $n-1$ dark cusps, if $m=(n-1)(n+1)$ we see $n-1$ grouping shuffled by multiplication by $n$ and this periodicity can not occurred if $m<(n-1)(n+1)$. So yes, $n^2-1$ is the first instance in which the ultimate pattern unambiguously appear.