本来没有欧拉反演这个名字的，只不过大家习惯性称之为欧拉反演
所谓欧拉反演其实就是利用欧拉函数的一条性质
\(\begin{aligned}n=\sum_{d|n}\varphi(d)\end{aligned}\)
我们试着把 \(n\)换成其他东西试试
\(\begin{aligned}gcd(i,j)=\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d|i}\sum_{d|j}\varphi(d)\end{aligned}\)
让我们求个东西试试
\(\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{i=1}^n\sum_{d|i}\sum_{d|n}\varphi(d)=\sum_{d|n}\sum_{i=1}^n\sum_{d|i}\varphi(d)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}\) 把它重写一遍作为结论
\(\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}\)