Primes of the form $p = (x_1 + x_2 + x_3 + x_4)\cdot(x_1 + x_2 - x_3 - x_4)\cdot(x_1 - x_2 + x_3 - x_4)\cdot(x_1 - x_2 - x_3 + x_4) $ The group detereminant was defined by Dedekind and a theorem was proved by Frobenius (https://en.wikipedia.org/wiki/Frobenius_determinant_theorem).
For instance if $G=C_2$ then the group matrix is given by:
$X_G = \begin{pmatrix}
x & y\\ 
y & x
\end{pmatrix}$. It has determinant $\det(X_G) = x^2-y^2$.
The question: For which natural numbers $n$ do we have $n = x^2-y^2$ is given by Fermat where he says that every odd number has such a presentation and this is used in Fermat factorization.
Now we want to make things a little more complicated and hopefully also more interesting:
Let $G$ be the Klein Four group. Then the group matrix of $G$ is given by:
$X_G=\begin{pmatrix}
 x_1& x_2 &x_3  &x_4 \\ 
 x_2&  x_1& x_4 & x_3\\ 
 x_3&  x_4& x_1 & x_2\\ 
 x_4&  x_3& x_2 & x_1
\end{pmatrix}
$ It has determinant $\det(X_G) = (x_1 + x_2 + x_3 + x_4)\cdot(x_1 + x_2 - x_3 - x_4)\cdot(x_1 - x_2 + x_3 - x_4)\cdot(x_1 - x_2 - x_3 + x_4)$
If one asks the question:
For which natural numbers $n$ do we have $n=\det(X_G)$ then because of a theorem from Dedekind we have $nm=\det(X_G)\cdot\det(Y_G) = \det(X_G\cdot Y_G) = \det(Z_G)$ hence it is enough to ask for which primes $p$ do we have such a representation.
For $G=$ Klein four group and $p\equiv 1 \mod(4)$ we have a solution:
$x_1=x_2=x_3=\frac{p-1}{4}$, $x_4=\frac{p+3}{4}$ which might be verified with your favorite algebra system (I recommend SAGE).
Now my question is: Let $p \equiv 3 \mod(4)$ be a prime.
Is it true, that $\det(X_G) = p$ has no solutions in natural numbers? If so, how to prove it? (I have a straightforward idea on how one might prove this, but it would be interesting to compare different solutions to this problem).
 A: We prove that any odd prime works if the product is allowed to be prime up to a sign, but that the product being positive (as prime numbers are) ensures the achievable prime values are those of the form $4k+1$ as you conjectured.
Setting three factors to $\pm 1$ and the fourth to $\pm p$ with $p\in\mathbb{P}$ is equivalent to solving $M\mathbf{x}=\mathbf{y}$, where the vector $\mathbf{y}$ can take one of $16$ values (we can place $p$ in one of four positions and apply one of two signs freely to two entries so the other sign is then determined by the requirement that the entries' product is positive so as to be prime; we don't consider cases where an entry is $-p$, since if this works we can multiple the whole vector by $-1$). The matrix $M$ satisfies $M^{-1}=\frac{1}{4}M$, so $\mathbb{x}=\frac{1}{4}M\mathbb{y}$. We thus get a solution iff each entry of $M\mathbb{y}$ is a multiple of $4$.
The first such constraint is $4|y_1+y_2+y_3+p$ if without loss of generality $y_4\ne 1$, but since each $y_1=\pm 1$ we can set $\sum_{i=1}^3 y_i$ to any odd integer from $-3$ to $+3$, so any odd $p$ can be made to work for a suitable choice of $\mathbb{y}$ (whereas $p=2$ cannot). Relative to this constraint, each other constraint subtracts twice the sum of some two $y_i$, requiring only that each such pair have the same parity, which certainly works for any odd $p$.
Thus the only remaining difficulty in achieving a given odd prime value for the product is ensuring we don't get $-p$ instead. For $y_1=y_2=y_3=1,\,y_4=p\in\mathbb{P}\backslash\{ 2\}$ each of the constraints checks either $p+3$ or $1-p$ or $p-1$ for divisibility by $4$, so that's the $p=4k+1$ case ticked off. With $p=4k-1$ we can't make it work, since the first constraint requires either $4|p+3$ or $4|p-1$.
