MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Fix some integer $n$. I would like to know when it is possible to find a cube root of 1 mod $n$, say $r$, so that it is possible to write

$m = a(r^{2} - 1) + b(r - 1) + c$ mod n

for all $0 \leq m \leq n-1$, with coefficients $a$, $b$ and $c$ that are `small'. I am not so picky about what small should mean, but am broadly looking for theorems like 'for $n$ in infinite family $A$, it is possible to find such $r$ with all coefficients $a,b,c = O(n^{0.6})$'. I'm also happy for theorems stating that there are no such $r$.

Thanks for any help.

EDIT in response to Kevin Buzzard: Thanks for the response, and I'm sorry for being unclear. I agree that that is one example of an infinite family of choices of $n$ and $r$ with good properties. I am trying to understand what types of behaviour are possible, and maybe it would be especially nice to know about an infinite family that was fairly dense. Maybe there is even a literature that would help one figure out this type of question - certainly I'm having a lot of trouble trying to figure out plausible guesses, or what values of $n$ are likely to be in families together, and so on.

The small number of other families I know about are:


1) Small modifications of your example (e.g. $A$ is parameterized by odd r, $n = \frac{r^{3} - 1}{2}$)


1) r = 1, any n 2) r = 6k+1 or 12k +1, n = 18k

Also, thanks to Felipe, that is a very nice family, and one I was not aware of.

share|cite|improve this question
Isn't this just trivial: can't I let $r$ be any positive integer, set $n=r^3-1$ and then I can get $a,b,c=O(r)=O(n^{1/3})$? – Kevin Buzzard Mar 24 '12 at 17:55

If $n$ is prime and $\equiv 1 \mod 3$, you don't need $r^2$ since $r^2+r+1=0$. So you can take $a=0$ and you can have $b,c = O(n^{1/2})$, since if two such numbers are congruent mod $p$, then their difference is zero and taking the norm of the corresponding Eisenstein integer, gives you a contradiction. So there is your $A$.

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.