A question on discrete Fourier transform of some function

Question

Let $\sigma(n) = \sum_{d|n} d$ and $\tau(n) = $ number of divisors of $n$.

For each $k, 0 \le k \le n-1$ we can look at the discrete Fourier transform of the numbers $\sigma(\gcd(n,k))$ given by:

$$\hat{\sigma}(k) = \sum_{l=0}^{n-1} \sigma(\gcd(n,l))\exp\left(\frac{-2 \pi i k l }{n}\right)$$

I implemented this in SAGEMATH, and it occured me that :

Conjecture: $$\hat{\sigma}(k) = n \tau(\gcd(n,k))$$

Is there any way to prove this?

Here is some sage-code which implements this:

def tau(n):
    return len(divisors(n))

def FTS(n,k):
    # Fourier Tranformierte von sigma(gcd(n,k))
    return sum([ sigma(gcd(n,l))*exp(-2*pi*I/n*k*l ) for l in range(n)])

N = 8
for k in range(N):
    print k,abs(FTS(N,k).N()),N*tau(gcd(N,k))

which gives:

0 32.0000000000000 32
1 8.00000000000000 8
2 16.0000000000000 16
3 8.00000000000000 8
4 24.0000000000000 24
5 8.00000000000000 8
6 16.0000000000000 16
7 8.00000000000000 8

Edit: From the conjecture above it follows, that, by setting $k=0$: $$\tau(n) = \frac{1}{n}\sum_{l=0}^{n-1} \sigma(\gcd(n,l))$$ for which I have a proof. By taking the inverse Fourier transform, and setting again $k=0$ we get: $$\sigma(n) = \sum_{l=0}^{n-1} \tau(\gcd(n,l))$$

Answer 1

$$\hat{\sigma}(k)=\sum_{l=1}^n \sigma(gcd(l,n)) e^{-2i \pi lk/n} = \sum_{d | n}\sum_{l=1, gcd(l,n)=d}^n \sigma(d)e^{-2i \pi lk/n}$$ $$ = \sum_{d | n}\sigma(d)\sum_{m=1,gcd(m,n)=1}^{n/d} e^{-2i \pi mk/(n/d)}=\sum_{d | n}(\sum_{r | d} r)(\sum_{l | \frac{n}{d}}\mu(l)\sum_{m=1}^{n/(dl)} e^{-2i \pi mk/(n/dl)})$$ This is a Dirichlet convolution of $4$ arithmetic functions and $1$ and $\mu$ cancel each other obtaining

$$= \sum_{r | n} r\sum_{m=1}^{n/r} e^{-2i \pi mk/(n/r)} = \sum_{r | n} r \frac{n}{r} 1_{ \frac{n}{r} | k} = n \tau(gcd(n,k))$$