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 us fix a positive natural number $N$. When $i$ is a natural number smaller than $N$, coprime with $N$, we let $\mu(i)$ be the unique number in $\{1, \ldots, N-1\}$ that is the multiplicative inverse of $N-i$ modulo $N$. I would like to know what is the maximum, when $i$ is in the range of the numbers from $1$ to $N-1$ that are coprime with $N$, of the function $f(i):=i+\mu(i)$.

share|cite|improve this question
What about $\left(N-1\right)+\left(N-1\right)$ ? The question might be more interesting for the function $i+\mu\left(-i\right)$. – darij grinberg Sep 9 '11 at 21:43
Sorry darij, this was what I meant. – Mathoverflow Sep 9 '11 at 22:03
I have edited the question after darij's observation. – Mathoverflow Sep 9 '11 at 22:05
By symmetry it's $2N$ minus the minimum of $i + \mu(i)$. If we imagine that the points $(i,\mu(i))$ are randomly distributed in the square of size $N$, we expect the minimum to be of order $N / \sqrt{\phi(N)}$. Proving something like this is probably asking too much, but using upper bounds on Kloosterman sums one gets $O(N^{3/4})$ when $N$ is prime (see e.g., and with some more work one can probably prove $O_\epsilon(N^{\frac34 + \epsilon})$ in general. – Noam D. Elkies Sep 9 '11 at 22:24
[Indeed we shouldn't expect it to be $O(sqrt{N})$ even for $N$ prime, because that requires that $cN-1$ have a factor $O(\sqrt{N})$ for some $c = O(1)$; but $N^{1/2+\epsilon}$ might still be true.] – Noam D. Elkies Sep 9 '11 at 23:27

Your Answer


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

Browse other questions tagged or ask your own question.