Non-standard Gauss sums I have the following problem. Let $p$ be some prime. What is the value of 
\begin{equation}
\sum_{k=1}^{p-1} \left(\frac{k+1}{p}\right) \omega_p^{kl},
\end{equation}
where $\left(\frac{k+1}{p}\right)$ is the Legendre symbol, and $\omega_p = e^{\frac{2\pi i}{p}}.$ [solved].
But what is the value of
\begin{equation}
\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}?
\end{equation}
I found the standard result for $\left(\frac{k}{p}\right)$, $\sqrt{p}$ or $i\sqrt{p},$ but I don't know the proof techniques and therefore don't know how to approach this one. Any ideas? I am not specialist in number theory, and I don't even know if it is easy or hard question :)
Any hints or links to references are welcomed.
What I actually need is the value (or a lower bound of the absolute value) of a Gauss sum with $\chi(k) = (\left(\frac{k}{p}\right)+1)(\left(\frac{k+1}{p}\right)+1).$
 A: We may assume that $l\not\equiv 0\pmod p$ because otherwise the given sum is simple. The answer is a Kloosterman sum.
Let $$\delta_q(x)=\begin{cases}
1,& \text{if } x\equiv 0\pmod{q};\\
0,& \text{if } x\not\equiv 0\pmod{q}.\\
\end{cases}$$
Then
\begin{gather*}
S(l)=\sum\limits_{k=1}^{p}\left(\dfrac{k(k+1)}{p}\right)e\left(\dfrac{kl}{p}\right)=\\=
\sum\limits_{k=1}^{p}\left(\sum\limits_{y=1}^{p}\delta_p(k(k+1)-y^2)-1\right)e\left(\dfrac{kl}{p}\right)=\\=
\sum\limits_{k,y=1}^{p}\delta_p(k(k+1)-y^2)e\left(\dfrac{kl}{p}\right)=[k=x+y]=\\=
\sum\limits_{x,y=1}^{p}\delta_p(x^2+2xy+x+y)e\left(\dfrac{(x+y)l}{p}\right).
\end{gather*}
For each non-zero summand $y=\dfrac{x^2+x}{2x+1}$. Hence
\begin{gather*}
S(l)=
\sum\limits_{\substack{1\leq x\leq p\\x\neq (p-1)/2}}e\left(\dfrac{l}{p}\cdot\left(\dfrac{x^2+x}{2x+1}+x\right)\right)=[t=2x+1]=\\=
\sum\limits_{t=1}^{p-1}e\left(\dfrac{l}{p}\cdot\left(\dfrac{3t}{4}-\dfrac{1}{4t}-\dfrac{1}{2}\right)\right),
\end{gather*}
where the expression $\dfrac{3t}{4}-\dfrac{1}{4t}-\dfrac{1}{2}$ is understood modulo $p$.
A: In the ring $\mathbb{Z}[\omega_p]$, the OP's second sum $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ raised to the $p$-th power is congruent to 
$\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)$ modulo $p$. This new sum consists of $p-2$ terms, each equal to $\pm 1$, hence it is invertible modulo $p$ in $\mathbb{Z}$ (hence also in $\mathbb{Z}[\omega_p]$) when $p>2$. We conclude that the OP's second sum is a nonzero element of $\mathbb{Z}[\omega_p]$, which can be turned into an exponential lower bound, and perhaps even a better one (see here for a related discussion).
P.S. This argument was inspired by Alexey Ustinov's response to the OP's question and Noam Elkies's response here, more precisely by Lucia's comment to Noam Elkies's response.
Added 1. As Alexey Ustinov remarked below, $\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=-1$. In fact this follows from his response to the OP's question by setting $l=0$ there and making the obvious modifications.
Added 2. Here is a slight variation of the above argument. The sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are Galois conjugates in the cyclotomic field $\mathbb{Q}(\omega_p)$, while their sum equals
$$ \sum_{l=1}^{p-1}\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}=-\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=1.$$
Hence all the sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are nonzero. Moreover, their product is a nonzero rational integer, which also implies (by bounding the relevant Kloosterman sums from above) that each of them has length
$$ \left| \sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}\right|>(4p)^{(2-p)/2}.$$
