Given a prime number $p$ and a primitive root $a$ modulo $p$, let
$\sigma\_{a,p}$ denote the permutation of the set $\{1, \dots, p-1\}$ which
maps $b$ to $a^b$ modulo $p$. 


**Question:** Let $p$ be fixed. Does the following hold?:


* If $p$ is congruent to $1$ modulo $4$, then for precisely half of the
primitive roots $a$ modulo $p$, the permutation $\sigma\_{a,p}$
is odd, and for the other half of the primitive roots it is even.
* If $p$ is congruent to $3$ modulo $4$, then either all permutations
$\sigma\_{a,p}$ are odd, or all of them are even -- depending on whether
$p$ divides $\frac{p-1}{2}!-1$ or not.



Sign of permutation induced by modular exponentiation
Your second guess is also correct. 


At first, we write down the sign of the permutation $\sigma\_a$ as the product $\prod\_{1\leqslant i<j\leqslant p-1}\frac{a^j-a^i}{j-i}$ modulo $p$. The denominator equals $(p-2)!(p-3)!\dots 1!$, and denoting $p=2m+1$ ($m$ is odd) we write it as $m!\prod\_{j=1}^{m-1} j!(p-1-j)!=m!\prod\_{j=1}^{m-1} (-1)^{j+1}=m!(-1)^{(m-1)/2}$. Here $m!$ appears, good.


Now for the numerator. We consider the polynomial $F(x)=\prod\_{1\leqslant i<j\leqslant p-1} (x^j-x^i)$ modulo the cyclotomic polynomial $\Phi\_{p-1}(x)$. We may write $F(x)=h(x)\Phi\_{p-1}(x)+r(x)$ for polynomials $h,r$ with integer coefficients, $\deg r<\varphi(p-1)$, and of course $F(a)$ and $r(a)$ are congruent modulo $p$. So our goal is to find $r$. For this we substitute the *complex* root $\omega=e^{2\pi i/(p-1)}$ of $\Phi\_{p-1}$ and get $r(\omega)=F(\omega)$. $F(\omega)$ may be calculated by the following (not original, in particular it is used for calculating the sign of Gauss sums) trick: at first, we know the argument of $F(\omega)$, since we know the argument $\frac\pi{2}+\frac\pi{2m}(k+j)$ of each bracket $\omega^k-\omega^j,1\leqslant j<k\leqslant p-1$, and they are easily summed up to $\pi(m-1)/2$ modulo $2\pi$. At second, we know $F^2(\omega)$. Indeed, using the formula 
$$\prod\_{j\ne i} (\omega^i-\omega^j)={\frac{t^{p-1}-1}{t-\omega^i}}|\_{t=\omega^i}=-(p-1)\omega^{-i},$$
the substitution is done by L'Hôpital rule; we get


$$
F^2(\omega)=-\prod\_i\prod\_{j\ne i} (\omega^i-\omega^j)=-(p-1)^{p-1}\omega^{-p(p-1)/2}=(p-1)^{p-1}.
$$


Thus $r(\omega)=F(\omega)=(-1)^{(m-1)/2} (p-1)^{(p-1)/2}$, where the sign is obtained from the previously found argument of $F(\omega)$. Since $\deg r<\varphi(p-1)=\deg \Phi\_{p-1}$ and $\Phi\_{p-1}$ is irreducible, we conclude that $r=(-1)^{(m-1)/2} (p-1)^{(p-1)/2}$ identically and modulo $p$ we get $r(a)=(-1)^{(m+1)/2}$.


Thus totally the sign of $\sigma\_a$ is $-m!$ modulo $p$.


