# Order of difference of two generators of cyclic group

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$?

-
Finite fields and polynomials are irrelevant here, no? You're just taking two generators of the cyclic group of order $2^n-1$, and asking about the order of their quotient. – Gerry Myerson Mar 10 '13 at 21:53
Thank you, that's much simpler. – Seraj Mar 10 '13 at 22:03
The order can be any number dividing $2^n-1$, assuming no knowledge about $\alpha$ and $\beta$. – Will Sawin Mar 10 '13 at 22:18
The only knowledge is that they are primitive roots themselves. I would be happy to see results with additional hypotheses however. – Seraj Mar 10 '13 at 22:21

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)$).