MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.