# Sum of floor function $\pmod{n}$

Let $n$ be a positive integer. Let $a$ be a nonzero integer such that $\gcd(a,n)=1$.

How to show that $$\frac{a^{\phi (n)}-1}{n} \equiv \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor \pmod{n}$$ where $i$ runs over all positive integers which are less than $n$ and relatively prime to $n$?

Remark: I find that if we take $a=2$ and $n=p$ where $p$ is an odd prime, then we can answer this question : congruent to mod p $1^{p-2}+2^{p-2}+\cdots+\left(\frac{p-1}{2}\right)^{p-2}\equiv\frac{2-2^p}{p}\pmod p.$.

EDIT:I just find out that this problem is stated in :

M. Lerch, “Zur Theorie des Fermatschen Quotienten. . . ,” Math. Ann. 60 (1905) 471–490. (when $n$ is a prime)

Using similar method, I can showed that:

$\phi (n) \frac{a^{\phi (n)}-1}{n} \equiv \phi (n) \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor \pmod{n}$ so the result is true when $\gcd (\phi (n) ,n)=1$. It seems that my problem is stated on page 487,equation $(30)$ of the paper. Since I don't understand German , I may miss something of the paper. Can someone explain to me that the techniques the author used?

-
What more do you know about this question? Did you come across it somewhere? Where? –  Gerry Myerson Jul 1 '12 at 8:57
I find this problem in:artofproblemsolving.com/Forum/… –  Ben Jul 1 '12 at 9:13
In the paper you cite equation (36) is preceded by the qualification "Moduli $m$ which satisfy the condition (35)..." i.e. that $\gcd(\phi(m),m)=1$, and preceding condition (35) on the previous page "if $\phi(m)$ is relatively prime to $m$...we can divide by $\phi(m)P(m)$," so it looks like you have already reached the same result. –  Zander Jul 1 '12 at 14:59
@Zander:Oh, thanks for your translation:) Now it seems that the trick given in the paper is not sufficient to this problem.I have to work on the case when $(n, \phi (n) )>1$ now... –  Ben Jul 2 '12 at 1:35