Question

Let $n\in\mathbb{Z}^+$ and $\alpha,\beta $ be two generators of the cyclic group $\left(\frac{\mathbb{Z}}{(2^n - 1)\mathbb{Z}},+\right)$.

Question: What are known theorems regarding the order of $\alpha-\beta$?

Answer 1

The way I would solve this problem (spoiler alert: I'm only going to start a solution, not carry it all the way through) is as follows. Let $m$ be the order of the cyclic group (here $m=2^n-1$, but the more general problem is no harder), and let $k$ be any divisor of $m$. Let $f(k)$ denote the number of ordered pairs of generators $(\alpha,\beta)$ of the cyclic group such that $k(\alpha-\beta)=0\pmod m$. Let $h(k)$ denote the number of such ordered pairs such that $\alpha-\beta$ has order exactly $k$. It's clear that $f(k) = \sum_{b\mid k} h(b)$, and so Möbius inversion gives $h(k) = \sum_{a\mid k} f(b) \mu(k/a)$. Therefore it suffices to find a formula for $f(k)$.

Let $g(\alpha)$ be the indicator function of generators of the cyclic group. Since $\alpha$ is a generator exactly when $\gcd(\alpha,m)=1$, we see that $$ g(\alpha) = \sum_{d\mid \gcd(\alpha,m)} \mu(d). $$ Therefore \begin{align*} f(k) &= \sum_{1\le\alpha\le m} g(\alpha) \sum_{1\le b\le m/k} g(\alpha+kb) \\ &= \sum_{1\le\alpha\le m} \sum_{c\mid \gcd(\alpha,m)} \mu(c) \sum_{1\le b\le m/k} \sum_{d\mid \gcd(\alpha+kb,m)} \mu(d) \\ &= \sum_{c\mid m} \mu(c) \sum_{d\mid m} \mu(d) \sum_{\substack{1\le\alpha\le m \\ c\mid \alpha}} \sum_{\substack{1\le j\le m/k \\ d\mid(\alpha+jk)}} 1. \end{align*} The inner double sum is a counting problem, and it will depend upon the common factors of $c$, $d$, and $k$, but it should be doable. And then the formula for $f(k)$ should reduce to some multiplicative-function-type sum (hence so will that for $h(k)$).