Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
6  
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. math.harvard.edu/~elkies/M229.09/kloos.pdf), 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
1  
[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

 
discard

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

Browse other questions tagged or ask your own question.