$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos{\left(\frac{2\pi}{M}kj\right)}=-M/2 $ I'm trying to proof something right now. What exactly is not important. I was able to break down the whole thing to the following equation.
$
\sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos{\left(\frac{2\pi}{M}kj\right)}=-M/2
$
This should hold for all even values of $M\in\mathbb{N}$. Any ideas? I tried to substitute both summation by a single one, but that yields to a big mess....
I checked it in Mathematica with different values of $M$.
 A: Change to exponential notation.  Let $j$ be fixed and let $d=\gcd(j,M).$  Then $$\sum_{k=1}^{M-1} \exp(2\pi i j k/M)$$ adds up some $M$-th roots of unity.  If you were to increase the upper limit to $M$, then you'd be adding all the $M/d$-th roots of unity $d$ times, which adds to $0$.  So: 
$$\sum_{k=1}^{M-1} \cos(2\pi j k/M) = \Re\left(\sum_{k=1}^{M-1} \exp(2\pi i j k/M)\right)$$ 
$$= \Re\left(\sum_{k=1}^{M} \exp(2\pi i j k/M) -\exp(2\pi i jM/M)\right) 
= \Re(0 - 1) = -1.$$  And that should make the outer sum easy.
A: First, We know that 
$$ \cos x = \frac{e^{ix}+e^{-ix}}{2}$$
Now assume $$ x = \frac{2\pi ji}{M} $$
We can rewrite given expression as
$$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{j=1}^{M/2}\sum_{k=1}^{M-1} \frac{e^{xk}+e^{-xk}}{2}$$
Let us first try to find value of 
$$ \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} $$
Notice that in your expression $k$ is starting from $1$ but it is starting from $zero$ now.
$$ \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} = \frac{1}{2}(\frac{e^{xM}-1}{e^x-1} - \frac{e^{-xM}-1}{e^x-1})$$
If with put the value of $ x=\frac{2\pi ji}{M} $ in $ e^{xM} $
we get $$ e^{xM} = e^{\frac{2\pi ji}{M}M} = e^{2\pi ji} = 1$$
Similarly $$ e^{-xM} = 1 $$
And therefore $$  \sum_{k=0}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} = 0 = 1 + \sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M})$$
$$ \Rightarrow \sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = -1 $$
Hence,
$$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{j=1}^{M/2}-1 = \frac{-M}{2}$$
A: When $j<M$, $kj\bmod M$ is a permutation of the integers $0,1,\cdots M-1$.
Then by cancellatoin of the quadrants,
$$\sum_{k=0}^{M-1}\cos\frac{2\pi kj}{M}=0$$ and
$$\sum_{k=1}^{M-1}\cos\frac{2\pi kj}{M}=-1.$$
The claim trivially follows.
