Is $|\{(j,k):\ 1\le j(k^{16}\ \text{mod}\ p)\}|$ even for each prime $p\equiv1\pmod {16}$? In my paper http://arxiv.org/abs/1809.07766, I determined the parity of
$$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^2\ \text{mod}\ p)>(k^2\ \text{mod}\ p)\right\}\right|$$
for any prime $p\equiv3\pmod4$, where $(a\ \text{mod}\ p)$ denotes the least nonnegative residue of $a$ modulo $p$.
Based on my computation, I have the following three conjectures.
Conjecture 1. For any prime $p\equiv1\pmod4$, we have
$$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^4\ \text{mod}\ p)>(k^4\ \text{mod}\ p)\right\}\right|\equiv\left\lfloor \frac{p-1}8\right\rfloor\pmod2.$$
Conjecture 2. For any prime $p\equiv1\pmod8$, we have
$$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^8\ \text{mod}\ p)>(k^8\ \text{mod}\ p)\right\}\right|\equiv\left|\left\{1\le k<\frac p4:\ \left(\frac kp\right)=1\right\}\right|\pmod2.$$
Conjecture 3. For any prime $p\equiv1\pmod{16}$, we have
$$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^{16}\ \text{mod}\ p)>(k^{16}\ \text{mod}\ p)\right\}\right|\equiv0\pmod2.$$
QUESTION. How to prove Conjectures 1-3?
The conjectures might not be very difficult. Maybe some of you could prove them. Your comments are welcome!
 A: Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually). 
Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of 
$$
A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p).
$$
Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction
$$
B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}}
$$
equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$). 
We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)=
(-1)^{{m/2 \choose 2}}
(m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ 
Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.
Start with the numerator. It is
$$
A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}).
$$
Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, 
$1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get 
once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$.
Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$
since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$.
The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.
Next, 
$$
\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})=
\prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2})
\cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}.
$$
The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$
\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m!
$$
For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)
Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs 
$$1\leqslant j<k\leqslant m\,\,\,\text{for which}\,\,\, j\equiv \eta\cdot k \pmod p.\quad (\ast)$$ Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$
Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ satisfies $(\ast)$. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get 
$$
(-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right)
$$
by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.
In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and 
$$
(-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}.
$$
Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.
