I was looking at the Wikipedia page for the totient function and stumbled across this fact. (https://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform)
The totient is the discrete Fourier transform of the gcd, evaluated at 1.[16] Let
$${\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}$$ where $x_k = gcd(k,n$) for $k ∈ {1, ..., n}$. Then
$${\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}$$
I tried reading the cited paper (http://math.colgate.edu/~integers/i50/i50.pdf), but frankly I don't quite understand. Looking for a proof that is more clear, or at least indicates what topics I should look into to understand why this would be true.