I need to find the number of regular $n$-polygons on $n$ equidistant points on a circle (that is, adjacent points are equally distant from each other). There's a hint saying the answer is related to the totient function.
What confuses me is that this question was given after we studied linear recurrence relations, and I can't think of any way to use them here.
The only thing I can think of is that we have such an $n$-polygon precisely when every $1\leq k\leq n$ coprime to $n$, and then divide by two because we count each such polygon twice...
Let $v_0,v_1,\ldots,v_{n-1}$ be equally spaced points wrapping around a circle in consecutive order. In how many ways can a regular polygonal path connect them all in a circuit?
If $n=1,2$ then no nondegenerate polygon (or circuit) is possible, so assume $n\ge 3$.
By regularity the chords connecting any pair of the points $v_i,v_j$ in a circuit will all have the same length and subtend equal central angles. This means there exists $1 \le k \lt n$ such that $j = (i+k) \bmod n$.
There are two claims to show, that such $k$ is coprime to $n$ and that $k_1$ and $k_2$ correspond to the same polygonal edges just when $k_2 = n - k_1$.
For the first of these note that if $d = \gcd(k,n)$, then only $n/d$ edges (chords) are needed to form a circuit from $v_0$ back to itself. In order for the circuit to include all $n$ points, we require $d=1$. Thus $k,n$ are coprime.
Thus there are $\phi(n)$ possibilities for $k$, where $\phi$ is Euler's totient function.
Finally two distinct "strides" $k_1,k_2$ around the circle give different polygons exactly when chords subtend unequal angles and have different lengths. Otherwise $k_1 + k_2 = n$ and we get equal chord lengths. Note that since $k$ is coprime to $n$, we never have $k = n-k$.
This establishes the second claim, so that the number of coprimes $k$ to $n$ counts each regular polygonal circuit exactly twice.
Thus the number of regular polygonal circuits is $\phi(n)/2$, and for the sake of specificity we could always choose the lesser of $k$ and $n-k$ to describe the circuit.
In effect this proves in a geometric/combinatorial fashion that $\phi(n)$ is always even for $n\ge 3$, by virtue of this correspondence of polygons. However the same may easily be argued by number theory. If $n$ has an odd prime factor $p$, then $p-1$ is a factor of $\phi(n)$ (and thus even). Otherwise for $n\ge 3$ not to have an odd prime factor it must be that $n=2^m$ for $m\gt 1$, and again $\phi(n) = 2^{m-1}$ is even.