Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 us suppose we have a prime $p > 3$ and two primitive roots $g_1, g_2$ of $p$ with index functions $\nu_1$ and $\nu_2$ (so that $g_1^{\nu_1(n)} = n$). Also suppose that $ef = p-1$ is a (nontrivial) factorization.

In short, my question is: Why is it 'obvious' that the set $\{n \mid \nu_1(n) \equiv 0 \pmod e \}$ is the same as the set $\{ n \mid \nu_2(n) \equiv 0 \pmod e\}$?

The rest is just for context and motivation.

This comes up in a standard proof of the prime-modulus-only case of Dirichlet's Theorem on the density of primes in arithmetic progressions, but my justification of why this fact is true has always bugged me. Like many number theoretic arguments, it's sort of a trick. In particular, we need that $\sum_{(\nu(n) \equiv 0 \mod e)} \zeta^n$ is independent of the primitive root we use, where $\zeta = e^{2\pi i / p}$ is the first primitive $p$th root of unity and $\nu(n)$ denotes the index of $n$ relative to whatever primitive root we're using. One way to show that this is true is to just realize that the sum $\displaystyle \frac{1}{e}\sum_{x = 0}^{p-1} \zeta^{x^e}$ gives us the sum we want and is independent of $\zeta$. But there's no intuition behind this statement to me, really.

It's not true that shifted equivalence classes are also permutations of each other here, i.e. that the set $\{ n | \nu(n) \equiv j \pmod e \}$ for $j \neq 0$ will be independent of the primitive root in general. But the sort of trick that I know above doesn't shed light onto this. (Why doesn't the trick work here? If you boil it down, the trick relies on the fact that $\nu(x^e) = e \nu(x) \equiv 0 \pmod e$, and this doesn't work so well with $\nu(x^{e + 1})$.)

share|cite|improve this question
up vote 5 down vote accepted

We have $\nu_i(n)\equiv 0\pmod{e}$ iff the order of $n$ is a divisor of $f$. Or to put it more simply, $\nu_i(n)$ is a multiple of $e$ iff $n^f\equiv 1\pmod{p}$. Either form of the second condition is purely a property of $n$, and in particular has nothing to do with the primitive root chosen.

share|cite|improve this answer

Another way to put the answer by André Nicolas: the cyclic group $(\mathbf Z/p \mathbf Z)^\times$ only has a single (cyclic) subgroup of order $f=(p-1)/e$, and both congruences you gave necessarily describe this subgroup.

share|cite|improve this answer
Better! Too many years of teaching a first number theory course to students innocent of algebra. – André Nicolas Aug 29 '12 at 7:13
I had to sit on this a bit to really like this, but I really like this. Thank you - – mixedmath Aug 29 '12 at 22:50

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.