Question 37
Let $n$ be a positive integer and let $a$ be an integer with $\text{gcd}(a, n) = 1$. Prove that
$$
\begin{gathered}
\frac{a\varphi(n) - 1}{n} \equiv \sum_{\substack{j=1 \\ \text{gcd}(j,n)=1}}^{n} \frac{1}{aj} \left[ \frac{aj}{n} \right] \pmod{n},
\end{gathered}
$$
where $\varphi(n)$ is the Euler's totient function and $[x]$ is the greatest integer not exceeding $x$.
$$
\begin{gathered}
\frac{a\varphi(n) - 1}{n} \equiv \sum_{\substack{j=1 \\ \text{gcd}(j,n)=1}}^{n} \frac{1}{aj} \left[ \frac{aj}{n} \right] \pmod{n},
\end{gathered}
$$
where $\varphi(n)$ is the Euler's totient function and $[x]$ is the greatest integer not exceeding $x$.