Let $n$ be a positive integer. Let $a$ be an integer such that $\gcd (a,n)=1$. Prove that
\[\frac{a^{\phi (n)}-1}{n}=\sum_{i\in R}\frac{1}{ai}\left[\frac{ai}{n}\right]\pmod{n}\]
where $R$ is the reduced residue system of $n$ with each element a positive integer at most $n$.
Let $S(a) = \frac{a^{\phi(n)} - 1}{n}$ First note that $k^{\phi(n)}S(a) \equiv S(a) \equiv \frac{(ka)^{\phi(n)} - 1}{n} \equiv S(ka) \pmod n$ where $k \in R$. Now let $r_k$ be the residue of $ka$ when divided by $n$. Note that $ka = n\lfloor\frac{ka}{n}\rfloor + r_k$ so by binomial expansion we have \[S(ka) = \frac{(...)n^3 + (...)n^2\phi(n) + \phi(n)n\lfloor\frac{ka}{n}\rfloor (r_k)^{\phi(n)-1} + r_k^{\phi(n)} - 1}{n} \equiv \\ (...)n^2 + (...)n\phi(n) + \frac{\phi(n)\lfloor\frac{ka}{n}\rfloor}{r_k} \pmod n\]. Now summing over all $k \in R$ and dividing by $\phi(n)$, we get $S(a) \equiv \sum_{k \in R} \frac{\lfloor\frac{ka}{n}\rfloor}{r_k} \pmod n$. It suffices to note that $ka \equiv r_k \pmod n$ and we are done.