Harmonic congruence There are a number of interesting congruences for harmonic sums, not the least of which is Wolstenholme's theorem: $H_{p-1}:=\sum_{j=1}^{p-1}\frac1j\equiv 0\mod p^2$.
It appears that $\sum_{j=1}^{p-1}(-1)^{\binom{j}2}\frac1j\equiv 0\mod p$ when $p\equiv1\mod 4$. Anyways, I ask for:

For a prime $p\geq5$, what is the value of
  $$\sum_{j=1}^{p-1}\frac{(-1)^{\binom{j}2}}j \mod p\,\,?$$

Contrast this with $\sum_{j=1}^{p-1}(-1)^{\binom{j}2}j=\frac{(-1)^{\binom{p}2}-1}2$ which equals $0$ when $p\equiv1\mod 4$ and equal $-1$ when $p\equiv3\mod4$.
 A: Let's use the fact that 
$$\frac{1}{j}\equiv \frac{(-1)^{j-1}}{p}\binom{p}{j}\pmod{p}$$
to rewrite your sum mod p as
$$\sum_{j=1}^{p-1}\frac{(-1)^{\frac{(j+2)(j-1)}{2}}}{p}\binom{p}{j}=\frac{1}{p}\left( \sum_{j=1}^{\frac{p-1}{2}}(-1)^{j-1}\binom{p}{2j-1} \right)+\frac{1}{p}\left( \sum_{j=1}^{\frac{p-1}{2}}(-1)^{j+1}\binom{p}{2j} \right)$$
$$=\frac{1}{2ip}\left((1+i)^p-(1-i)^p-2i^p\right)+\frac{1}{2p}\left(2-(1+i)^p-(1-i)^p\right)$$
$$=\frac{(1+i)^{p-1}-(1-i)^{p-1}+i-i^p}{ip}=\frac{2^{\frac{p-1}{2}}(i^{\frac{p-3}{2}}-(-i)^{\frac{p+1}{2}})+1-(-1)^{\frac{p-1}{2}}}{p}$$
and this can easily be checked to be zero for $p=1\pmod{4}$ and $\frac{2+2^{\frac{p+1}{2}}(-1)^{\frac{p-3}{4}}}{p}$ when $p=3\pmod{4}$.
A: For simplicity, let $p'=\lfloor\frac{p-1}2\rfloor, p''=\lfloor\frac{p-1}4\rfloor$ and the so-called Fermat's quotients $q_2=\frac{2^{p-1}-1}p$. Observe that
$$\sum_{k=1}^{p-1}\frac{(-1)^{\binom{k}2}}k
=\sum_{k=1}^{p'}\frac{(-1)^k}{2k}-\sum_{k=1}^{p'}\frac{(-1)^k}{2k-1}.$$
If we change variables $k\rightarrow p'-k+1$ then
$$\sum_{k=1}^{p'}\frac{(-1)^k}{2k-1}=\sum_{k=1}^{p'}\frac{(-1)^{p'-k+1}}{p-2k}
\equiv_p (-1)^{p'}\sum_{k=1}^{p'}\frac{(-1)^k}{2k}.$$
The following are known facts: $\sum_{k=1}^{p''}\frac1k\equiv_p-3q_2$ and
$\sum_{k=1}^{p'}\frac1k\equiv_p-2q_2$. Therefore, we have
\begin{align} \sum_{k=1}^{p'}\frac{(-1)^k}k
&=\sum_{k=1}^{p''}\frac1{2k}-\sum_{k=1}^{p''}\frac1{2k-1} 
=\sum_{k=1}^{p''}\frac1{2k}-\left(\sum_{k=1}^{p'}\frac1k-\sum_{k=1}^{p''}\frac1{2k}\right) \\
&=\sum_{k=1}^{p''}\frac1k - \sum_{k=1}^{p'}\frac1k\equiv_p-q_2. \end{align}
Going back to the earlier sums, we conclude that
$\sum_{k=1}^{p'}\frac{(-1)^k}{2k-1}\equiv_p-\frac12(-1)^{p'}q_2$ and
$$\sum_{j=1}^{p'}\frac{(-1)^{\binom{j}2}}j
\equiv_p\frac{(-1)^{p'}-1}2\,q_2 \equiv_p\frac{\left(\frac{-1}p\right)-1}2\,q_2;$$
where $\left(\frac{a}p\right)$ stands for the Legendre symbol.
