3
$\begingroup$

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:

Good:

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

Bad:

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.

$\endgroup$
1
  • $\begingroup$ 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})$? $\endgroup$ Mar 24, 2012 at 17:55

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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