The first step in the proof of the Pólya-Vinogradov Inequality. The well-known Pólya-Vinogradov Inequality states:
$$\forall m, n \in \mathbb{N}: \displaystyle \left|{\sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)}\right| < \sqrt p \ \ln p,$$
where $\left({\frac k p}\right)$ is the Legendre symbol.
I would like to write out a nice, detailed proof for personal reference, and I can follow most of the proofs I find well-enough, except for the first step. Many start with the same thing, or close to it:
"Start with the following manipulations: $$\displaystyle \sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)=\displaystyle \frac 1 p \sum_{k \mathop = 0}^{p-1} \sum_{x \mathop = m}^{m+n} \sum_{a \mathop = 0}^{p-1} \left({\frac k p}\right) e^{2 \pi i a \left({x - k}\right) / p}=\displaystyle \frac 1 p \sum_{a \mathop = 1}^{p-1} \sum_{x \mathop = m}^{m+n} e^{2 \pi i a x / p} \sum_{k \mathop = 0}^{p-1} \left({\frac k p }\right) e^{-2 \pi i a t / p}.$$
I have absolutely no idea where this first step comes from. I am especially confused as to why the index of summation changes from how it is originally presented. I am somewhat new to quadratic Gauss sums, which I understand are the whole basis for this. 
Thanks very much for any and all input.
 A: The key idea here is orthogonality: the complex number $\omega_r = e^{2\pi ir/p}$ has the property that $\omega_r^p = 1$.  This makes it easy to evaluate $\sum_{a=0}^{p-1} \omega_r^a$, since
$$(1 - \omega_r)(1 + \omega_r + \omega_r^2 + \cdots + \omega_r^{p-1}) = 1 - \omega_r^p = 0.$$
As long as $\omega_r \ne 1$, we can cancel out the first factor to obtain $\sum_{a=0}^{p-1} \omega_r^a = 0$.  On the other hand, if $\omega_r = 1$ it is trivial to evaluate the sum directly as $\sum_{a=0}^{p-1} 1 = p$, which gives the orthogonality relation:
$$ \sum_{a=0}^{p-1} e^{2\pi i ar/p} = \sum_{a=0}^{p-1} \omega_r^a = \begin{cases} p,&\text{if }r\equiv 0 \pmod p; \\ 0, &\text{otherwise}.\end{cases}.$$
Now it's easy to see how the sum unravels.  First, the ranges of summation are independent so we may freely switch the order of the sums:
$$ \frac 1 p \sum_{k \mathop = 0}^{p-1} \sum_{x \mathop = m}^{m+n} \sum_{a \mathop = 0}^{p-1} \left({\frac k p}\right) e^{2 \pi i a \left({x - k}\right) / p} = \frac 1 p \sum_{x \mathop = m}^{m+n} \sum_{k \mathop = 0}^{p-1}  \sum_{a \mathop = 0}^{p-1} \left({\frac k p}\right) e^{2 \pi i a \left({x - k}\right) / p}.$$
The innermost sum is exactly $0$ unless $k \equiv x \pmod p$, and since $k$ goes through a complete system of residues mod $p$ this occurs exactly once for each value of $x$, so we can restrict the sum to just the place where $k=x$.
$$\frac 1 p \sum_{x \mathop = m}^{m+n} \sum_{k \mathop = 0}^{p-1}  \sum_{a \mathop = 0}^{p-1} \left({\frac k p}\right) e^{2 \pi i a \left({x - k}\right) / p} = \frac 1 p \sum_{x \mathop = m}^{m+n} \sum_{k=x}^{x}  \left({\frac k p}\right) p = \sum_{x \mathop = m}^{m+n} \left({\frac x p}\right).$$
Since you're writing a detailed proof, note that even though $m,n$ might well be outside the range $[0,p)$, we can still justify restricting $k=x$ because both the Legendre symbol $(k/p)$ and the exponential term $e^{2\pi ia(x-k)/p}$ are periodic mod $p$.
