Solution with a1267ab. The key claim is the following characterization of $A$: \[ A=\{\omega+\omega^{-1}+2 \mid \omega^{2n}=-1\text{ for }\omega\in\mathbb{F}_{p^2}\}

as desired. Now, we show that every element of $A'$ is a QNR. First, suppose that $p\equiv1\pmod4$ so $n=\frac{p-1}{4}$. Then $\omega^{\frac{p-1}{2}}=-1$, so $\omega$ is a QNR in $\mathbb{F}_p$. Then $\omega+\omega^{-1}+2=\frac{(\omega+1)^2}{\omega}$ is also a QNR in $\mathbb{F}_p$ as desired. Next, suppose that $p\equiv3\pmod4$ so $n=\frac{p+1}{4}$. Then $\omega^{\frac{p+1}{2}}=-1$. Then \[ (\omega+\omega^{-1}+2)^{\frac{p-1}{2}}=\frac{(\omega+1)^{p-1}}{\omega^{\frac{p-1}{2}}}=\frac{(\omega+1)^p}{\omega^{\frac{p-1}{2}}(\omega+1)}=\frac{\omega^p+1}{\omega^{\frac{p+1}{2}}+\omega^{\frac{p-1}{2}}}=\frac{\omega^p+1}{-1-\omega^p}=-1 \]so $\omega+\omega^{-1}+2$ is a QNR in $\mathbb{F}_p$ as desired. Finally, observe that $A'=4-A'$ by pairing $\omega$ with $-\omega$. This implies that $A=A'$ as claimed. To finish, this implies that the elements of $A$ are the roots of $T_n\left(\tfrac{X-2}{2}\right)$, where $T_n$ is the $n$th Chebyshev polynomial. The leading coefficient of this is $\frac{1}{2}$ while the constant term is $T_n(-1)=(-1)^n$, so the product of the elements of $A$ is $2$.

We will be using finite field theory and the Frobenius endomorphism freely. Also we will just give a sketch and leave out details like it's out of fashion. Case 1: $p\equiv 3\pmod{4}$. Work in $\mathbb{F}_{p^2} = \mathbb{F}_p[i]$. Suppose $a\in A$. Then, $a=-x^2$ for some $x\in\mathbb{F}_p$ and $4-a=y^2$ for some $y\in\mathbb{F}_p$, so we have \[x^2+y^2 = -4.\]This factors as \[(x+iy)(x-iy) = (2i)^2,\]so we have $x+iy=2it$ and $x-iy=2i/t$ for some $t\in\mathbb{F}_p[i]$, so \[x=i(t+1/t)\quad\text{and}\quad y=t-1/t.\]For both of these to be in $\mathbb{F}_p$, we need $x^p=x$ and $y^p=y$, which when we work out with frobenius, tells us that $t^{p+1}+1=0$. Thus, if $a\in A$, we must have $a=(t+1/t)^2$ for some $t\in\mathbb{F}_p[i]$ such that $t^{p+1}+1=0$. Actually it is easy to see that if $t$ satisfies $t^{p+1}+1=0$, then both $a$ and $4-a$ are QNRs (just reverse the frobenius calculation above). Thus, \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{p+1}+1=0\}.\]Note $(t+1/t)^2 = (t'+1/t')^2$ if and only if $t'\in\{t,-t,1/t,-1/t\}$, and also $t^{p+1}+1=0\iff (t')^{p+1}+1=0$. Note that \[t^{p+1}+1\mid t^{p^2}-t\]as $2(p+1)\mid p^2-1$, so $t^{p+1}+1$ has distinct roots in $\mathbb{F}_p[i]$. We see that \[t^{p+1}+1=(t^{\frac{p+1}{2}}+i)(t^{\frac{p+1}{2}}-i),\]and $s$ a root of $t^{\frac{p+1}{2}}-i$ if and only if $1/s$ is a root. Thus, it is easy to see that \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{\frac{p+1}{2}}-i=0\}.\]In this parameterization, only $t$ and $-t$ produce the same value (and these never coincide as $t\ne 0$), so we actually have \[T:=\prod_{a\in A}=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}(t+1/t).\]This becomes \[T=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}\frac{(t+i)(t-i)}{t}.\]Letting $f(x)=x^{\frac{p+1}{2}}-i$, we see that this product becomes \[T=(-1)^{\frac{p+1}{4}}\frac{f(-i)f(i)}{f(0)}.\]It is tedious but straightforward to see that this always gives $2$. Case 2: $p\equiv 1\pmod{4}$. Let $\ell$ be some QNR mod $p$ (sadly we don't have any free QNRs like $-1$ is for $3\pmod{4}$ primes). Let $\omega$ be a formal square root of $\ell$, and work in $\mathbb{F}_{p^2} = \mathbb{F}_p[\omega]$. Then, if $a\in A$, we have \[\omega^2 a = x^2\quad\text{and}\quad\omega^2(4-a)=y^2,\]so $x^2+y^2=4\omega^2$, so factoring and doing the same as before, we get \[x=\omega(t+1/t)\quad\text{and}\quad y=\frac{\omega}{i}(t-1/t)\]for some $t\in\mathbb{F}_p[\omega]$. These are in $\mathbb{F}_p$ if and only if $t^{p-1}+1=0$ (using frobenius). We see $a=(t+1/t)^2$, so \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[\omega], t^{p-1}+1=0\}.\]Doing a similar analysis as before, the desired product becomes \[T:=\prod_{a\in A}=(-1)^{\frac{p-1}{4}}\prod_{\substack{t\in\mathbb{F}_p[\omega]\\t^{\frac{p-1}{2}}-i=0}}\frac{(t+i)(t-i)}{t},\]and letting $f(x)=x^{\frac{p-1}{2}}-i$, we get \[T=(-1)^{\frac{p-1}{4}}\frac{f(-i)f(i)}{f(0)},\]which again is always $2$. So the answer is $\boxed{2}$.

We first compute $|A|$. Note that $$|A| = \frac{1}{4}\sum_{a=1}^{p-1}\left(\left(\frac{a}{p}\right) - 1\right)\left(\left(\frac{4-a}{p}\right)-1\right)$$since the term in paranthesis is $4$ when $a\in A$, and $0$ otherwise. Now since all the Legendre symbols sum to $0$ we have $\sum_{a=1}^{p-1} \left(\frac{a}{p}\right) = 0, \sum_{a=1}^{p-1} \left(\frac{4-a}{p}\right)=-1$, and $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)\left(\frac{4-a}{p}\right) = \sum_{a=1}^{p-1} \left(\frac{a^{-1}}{p}\right)\left(\frac{4-a}{p}\right) =\sum_{a=1}^{p-1} \left(\frac{4a^{-1}-1}{p}\right) = -\left(\frac{-1}{p}\right)$$and thus $|A| = \frac{p-1}{4}$ if $p\equiv 1\pmod{4}$, and $\frac{p+1}{4}$ if $p\equiv 3\pmod{4}$. Define $A'$ to be the set of residues $a$ such that $\left(\frac{a}{p}\right) = \left(\frac{1-a}{p}\right)=-1$; there is a clear bijection $A'\rightarrow A$ given by $a\rightarrow 4a$, and thus $4^{|A|}\prod_{a\in A'} a = \prod_{a\in A} a$. It remains to find this latter product. We do this via casework on $p\pmod{4}$. If $p\equiv 1\pmod{4}$, then we instead look at the set $B$ of residues $b$ with $\left(\frac{1-b}{p}\right) = -1$, $\left(\frac{b}{p}\right) = 1$. In this case, it follows $$\left(\frac{(1-b)b^{-1}}{p}\right) = \left(\frac{b^{-1}-1}{p}\right) = \left(\frac{1-b^{-1}}{p}\right)=-1$$so every $b\in B$ can be paired with $b^{-1}\in B$. The only possible exception is $b=-1$, which is in $B$ if $\left(\frac{2}{p}\right)=-1$. It follows that $\prod_{b\in B} b = \left(\frac{2}{p}\right)$. Now if $C$ is the set of all residues $c$ with $\left(\frac{1-c}{p}\right)=-1$, it follows $\prod_{a\in A'} a = \prod_{c\in C} c/\prod_{b\in B} b$. Pick $s$ to be your favorite quadratic non-residue in $\mathbb{F}_p$; then $C = \{1-sx^2, 1\le x\le \frac{p-1}{2}\}$. Thus $$\prod_{c\in C} c = \prod_{x=1}^{\frac{p-1}{2}} (1-sx^2) = s^{-\frac{p-1}{2}} \prod_{x=1}^{\frac{p-1}{2}} (s-(sx)^2) = -\prod_{y=1}^{\frac{p-1}{2}} (s-y^2)$$since multiplying the set of quadratic residues by $s^2$ changes nothing. Take $\sqrt{s}$ to be an element of $\mathbb{F}_{p^2}$ whose square is $s$, and write $$\prod_{y=1}^{\frac{p-1}{2}} (s-y^2) = \prod_{y=1}^{\frac{p-1}{2}} (\sqrt{s}-y)(\sqrt{s}+y) = \prod_{y=1}^{p-1} (\sqrt{s}-y) = (\sqrt{s})^{p-1}-1 = s^{\frac{p-1}{2}}-1 = -2$$which implies $\prod_{c\in C} c = 2$. Thus $\prod_{a\in A'} a = 2\left(\frac{2}{p}\right)$. Now note $4^{|A|} = 4^{\frac{p-1}{4}} = 2^{\frac{p-1}{2}} = \left(\frac{2}{p}\right)$ so $\prod_{a\in A} a = 4^{|A|}\prod_{a\in A'} a = 2$. If $p\equiv 3\pmod{4}$, then our work is much simpler: if $a\in A$, then $$\left(\frac{(1-a)a^{-1}}{p}\right) = \left(\frac{a^{-1}-1}{p}\right) = -\left(\frac{1-a^{-1}}{p}\right) = 1$$so every $a\in A'$ can be paired with $a^{-1}\in A'$. The only possible exception, again, is $a=-1$, which is in $A'$ if $\left(\frac{2}{p}\right) = -1$. Therefore $\prod_{a\in A'} a = \left(\frac{2}{p}\right)$. On the other hand, now $4^{|A|} = 4^{\frac{p+1}{4}} = 2^{\frac{p+1}{2}} = 2\cdot 2^{\frac{p-1}{2}} = 2\left(\frac{2}{p}\right)$, so $\prod_{a\in A} a = 4^{|A|} \prod_{a\in A'} a = 2$. Thus in both cases, the answer is $\boxed{2}$.

We claim the answer is $2$, and we will prove this. Define $B$ as the set of integers $a$ such that $1\le a<p$ such that both $a$ and $4-a$ are quadratic residues, and define $C$ as the set of integers $a$ such that $1\le a<p$ such that either $a$ or $4-a$ (but not both) is a quadratic residue. Notice that every integer in $[1,p)$ in exactly one of $A,B$, or $C$, and $4\in B$. Define a "pear" as two distinct integers $a$, $b$ such that $1\le a<p$, $1\le b<p$, and $a+b\equiv 4 \pmod p$. Notice that $2$ and $4$ are not in a pear but all other integers in $[1,p)$ are in exactly one pear. Furthermore, two elements in a pear must be in the same set (of $A$, $B$, or $C$). Lemma 1: Let $x,y$ be a pear. Let $k$ be the residue mod $p$ of $xy$. Then if $x,y\in A$ or $x,y\in B$, then $k\in B$, and if $x,y \in C$ then $k \in C$. Proof of Lemma 1: Notice $$4-k\equiv 4-xy\equiv 4-x(4-x)=4-4x+x^2=(x-2)^2\pmod p.$$Thus, $4-k$ is always a quadratic residue. If $x,y\in A$ then both $x$ and $y$ are quadratic non-residues, so $xy$ is a quadratic residue, which implies $k$ is a quadratic residue and $k\in B$. If $x,y\in B$ then both $x$ and $y$ are quadratic residues, so $xy$ is a quadratic residue, which implies $k$ is a quadratic residue and $k\in B$. If $x,y\in C$ then exactly one of $x$ and $y$ is a quadratic residue, so $xy$ is a quadratic non-residue, which implies $k$ is a quadratic non-residue and $k\in C$, proving Lemma 1. Lemma 2: Let $k\neq 4$ be an element of $B$. Then there exists a unique pear $x,y$ such that $xy\equiv k \pmod p$, and the pear is in $A$ or $B$. Proof of Lemma 2: Recall $4-xy\equiv (x-2)^2 \pmod p$. Thus, $$xy\equiv k \pmod p\Longleftrightarrow (x-2)^2\equiv 4-k\pmod p.$$Let $z, p-z$ be the distinct residues mod $p$ such that $$z^2=(p-z)^2=4-k\pmod p,$$they exist since $k\in B$ and $4-k\neq 0$. Then we have either $x-2\equiv z\pmod p$ or $x-2\equiv p-z\pmod p$. So either $x\equiv z+2\pmod p$ or $x \equiv p-z+2$. If $x\equiv z+2\pmod p$, then $y\equiv p-z+2\pmod p$ and vice versa, so there is only one pear $x,y$. By Lemma 1, the pear is in $A$ or $B$. This concludes the proof of Lemma 2. We now split into 2 cases depending on if $2$ is in set $A$ or set $B$ ($2$ can not be in set $C$ since it is impossible for exactly one of $2,2$ to be a quadratic residue). Case 1: $2\in A$. Then $B=\{4,\text{pears}\}$, $A=\{2,\text{pears}\}$, and $C=\{\text{pears}\}$. Define $P_B$ as the product of all elements in pears in $B$, and $P_A$ as the product of all elements in pears in $A$. Then by Lemmas 1 and 2, we have $$P_B\cdot P_A\equiv P_B\pmod p.$$(This is because each element $\neq 4$ in $B$ can be matched with a pear in $A$ or $B$, there is a bijection). Since $0$ is not in $B$, $P_B \neq 0 \pmod p$ so $P_a\equiv 1 \pmod p$. Thus, the product of all elements in $A$ is $2\pmod p$, as desired. Case 2: $2\in B$. Then $B=\{4,2,\text{pears}\}$, $A=\{\text{pears}\}$, and $C=\{\text{pears}\}$. Define $P_B$ and $P_A$ as before. Then by Lemmas 1 and 2, we have $$P_B\cdot P_A\equiv 2\cdot P_B\pmod p.$$(This is because of the same bijection as in Case 1). Since $0$ is not in $B$, $P_B\neq 0 \pmod p$ so $P_a\equiv 2 \pmod p$. Thus, the product of all elements in $A$ is $2\pmod p$, as desired. We have shown the conclusion in all cases, and we are done.

18-page writeup I only give an outline.

We claim that the product is always $2$ modulo $p$. Assume $p\geq 5$. Define $B=\{b\ \vert\ 1\leq b\leq p-1, b \ \text{is a quadratic residue}\},$ $C=\{c\ \vert\ 1\leq c\leq p-1, 4-c \ \text{is a quadratic residue}\},$ $D=\{d\ \vert\ 1\leq d\leq p-1, d \ \text{and} \ 4-d \ \text{are quadratic residues}\}.$ In an abuse of notation, let $A=\prod_{a\in A}a$ and define $B, C, D$ similarly. It's easy to see that \[\frac{ABC}{D} \equiv (p-1)! \equiv -1\]by Wilson (all congruences will be taken modulo $p$). We have \[B \equiv \prod_{b=1}^{\frac{p-1}{2}}b^2 \equiv \left(\frac{p-1}{2}\right)!\equiv(p-1)!(-1)^{\frac{p-1}{2}}\equiv(-1)^\frac{p+1}{2}\]and \[C \equiv \prod_{\stackrel{c=0}{c\neq 2}}^{\frac{p-1}{2}}(4-c)^2\equiv\prod_{\stackrel{c=0}{c\neq 2}}^{\frac{p-1}{2}}(2-c)\prod_{\stackrel{c=0}{c\neq 2}}^{\frac{p-1}{2}}(2+c)\equiv \frac 12(-1)^{\frac{p-5}{2}}\left(\frac{p-5}{2}\right)!\left(\frac{p+3}{2}\right)!\equiv \frac 12 (p-1)!\equiv -\frac 12.\]Thus to show that $A\equiv 2$, it suffices to show that \[\frac{2BC}{D}\equiv -1 \iff D \equiv (-1)^{\frac{p+1}{2}}.\] Let's first parameterize $D$: Claim. If $x^2+y^2\equiv 4$ and $y\not\equiv 0$ then we can find an $m$ such that \[x \equiv \frac{2(m^2-1)}{m^2+1}, \ y\equiv \frac{4m}{m^2+1}.\]Proof. Verify that $m \equiv \pm \frac{2+x}{y}$ works for an appropriate choice of sign. \(\blacksquare\) Thus $D$ is the product of the distinct values of $\frac{16m^2}{(m^2+1)^2}$ over all nonzero $m$. Moreover, we can determine which values of $m$ produce the same values for $y^2$: Claim. $\frac{16m_1^2}{(m_1^2+1)^2}\equiv \frac{16m_2^2}{(m_2^2+1)^2}$ if and only if $m_2\in\{\pm m_1, \pm \frac{1}{m_1}\}$. Proof. It's easy to see that the two fractions are congruent if $m_2$ is one of the prescribed values. In the other direction, we can cross-multiply and verify that the congruence implies \[(m_1^2m_2^2-1)(m_1^2-m_2^2)\equiv 0\]which is enough. \(\blacksquare\) Before we evaluate $D$, let's prove the following useful polynomial identity: Claim. $(x-1^2)(x-2^2)\cdots \left(x-\left(\frac{p-1}{2}\right)^2\right)\equiv x^{\frac{p-1}{2}}-1.$ Proof. Note that the congruence holds whenever $x$ is a quadratic residue (a total of $\frac{p+1}{2}$ residues) while both sides have degree $\frac{p-1}{2}$. Then by Lagrange the difference between the two sides must be the zero polynomial, as desired. \(\blacksquare\) We first evaluate $D$ when $p\equiv 3 \pmod 4$ where $-1$ is not a quadratic residue. Suppose there are $M$ pairs of residues $1\leq a < b \leq \frac{p-1}{2}$ for which $ab\equiv -1$. Then we can verify that \[\left(\frac{p-1}{2}\right)!\equiv (-1)^M\]because each $1< a\leq \frac{p-1}{2}$ in the product can be paired with either its inverse or the negative of its inverse. For a similar reason we have \[D \equiv (-1)^M \cdot\ 4\prod_{m=2}^{\frac{p-1}{2}}\frac{4m}{m^2+1} \equiv (-1)^M \cdot\ 2\prod_{m=2}^{\frac{p-1}{2}}\frac{4m}{m^2+1}\equiv (-1)^M \cdot\ 2\prod_{m=1}^{\frac{p-1}{2}}\frac{m}{m^2+1}.\]This evaluates to \[(-1)^M\cdot 2\cdot \frac{\left(\frac{p-1}{2}\right)!}{(1+1^2)(1+2^2)\cdots \left(1+\left(\frac{p-1}{2}\right)^2\right)}\equiv (-1)^M\cdot 2\cdot \frac{(-1)^M}{(-1)^{\frac{p-1}{2}}(-2)}\equiv 1,\]as desired. If $p\equiv 1\pmod{4}$ then $-1$ is a quadratic residue; let $1<i\leq \frac{p-1}{2}$ satisfy $i^2\equiv -1$. Define $M$ as before; then we can check that \[\left(\frac{p-1}{2}\right)!\equiv (-1)^Mi.\]As polynomials, we also have \[\frac{1}{x-i^2}(x-1^2)(x-2^2)\cdots \left(x-\left(\frac{p-1}{2}\right)^2\right)\equiv \frac{x^{\frac{p-1}{2}}-1}{x+1}\equiv -1+x-x^2+\cdots + x^{\frac{p-3}{4}}\]which implies \[\prod_{\stackrel{m=1}{m\neq i}}^{\frac{p-1}{2}}(1+m^2)\equiv -\prod_{\stackrel{m=1}{m\neq i}}^{\frac{p-1}{2}}(-1-m^2)\equiv -(-1-1-\cdots -1) \equiv \frac{p-1}{2} \equiv -\frac 12.\]Finally \[D\equiv 2(-1)^M\prod_{\stackrel{m=1}{m\neq i}}^{\frac{p-1}{2}}\frac{4m}{m^2+1}\equiv \frac 12 (-1)^M\prod_{\stackrel{m=1}{m\neq i}}^{\frac{p-1}{2}}\frac{m}{m^2+1}\]which evaluates to \[\frac 12 (-1)^M \frac{\frac 1i \left(\frac{p-1}{2}\right)!}{-\frac 12}\equiv -(-1)^M\frac 1i (-1)^Mi \equiv -1.\]So we're done.

This solution relies on the fact that the number $4$ was chosen. The answer is $\boxed{2}$. Work in $\mathbb{F}_p$ and let $\text{QR}$ denote the set of quadratic residues. The main idea is to consider the sets $X = \{x \mid x(4-x) \in \text{QR}\}$ and $B = \{b \mid b(4-b) \in \text{QR}, b \in \text{QR}\}$. Clearly $X = A \cup B$ and $A \cap B = \emptyset$ because squareness is multiplicative in $\mathbb{F}_p$. Observe that $x(4-x) \equiv b \in \text{QR}$ iff $4 - (x-2)^2 \equiv b$ iff $4 - b \in \text{QR}$, i.e. $b \in B$. This means there is a natural $2$-to-$1$ correspondence between elements of $X \setminus \{2\}$ and $B \setminus \{4\}$ via $x, 4-x \mapsto b$ where $x$ is a solution to $x(4-x) \equiv b$. This mapping is clearly surjective and the preimage of every element in $B \setminus\{4\}$ has two elements. Let $P(S)$ denote the product of the elements of a set $S$. The above correspondence indicates that, barring the issue of multiplying by zero and the double root of $2$, $P(B)$ and $P(X)$ are the same because by definition, $x, 4-x \in X$ have the same product as their image. We can easily fix this by removing $0, 4$ from $B$ and their preimages from $X$. Let $B' = B \setminus\{0, 4\}$ and let $X' = X \setminus \{0, 2, 4\}$. Then we have the same correspondence as before from $X'$ to $B'$ but this time $P(B') = P(X')$ and both are not zero. Thus $$P(A)P(B') \equiv P(X \setminus\{0, 4\}) \equiv 2P(X') \implies P(A) \equiv 2,$$as desired.

how are you guys so fast?

Solution: The remainder is always \(2\). work modulo \(p\). Let \(T\) be the set of quadratic residues. Let \(S_1=\{a \mid a \neq 0, a \neq 4, a \in T,4-a \in T\}, S_2=\{a \mid a \notin T ,4-a \notin T\},\) and let \(S= S_1 \cup S_2\). Note \(S_1\) and \(S_2\) are disjoint. Claim 1: If \(a \in S\) and \(a \neq 2\), then \(a(4-a), (a-2)^2 \in S_1\). Note \(a \in S\) implies \(a\) and \(4-a\) are either both QR or both QNR, so \(a(4-a) \in T\). Since clearly \((a-2)^2 \in T\), the sum of \(a(4-a)\) and \((a-2)^2\) is \(4\), and \(a(4-a)\) and \((a-2)^2\) are not \(0\) unless \(a=0,2,4\), then the claim holds. Claim 2: \(|S| \ge 2|S_1|+1\). Take any number \(a \neq 2\) in \(S\), and take \((a-2)^2\). This number is in \(S_1\) by Claim 1, and each \((a-2)^2\) value can be produced at most twice by elements of \(S\), so \(|S|-1 \ge 2|S_1|\). We now evaluate the product \(\prod_{a \in S} a\). Pair up the pairs \((a,4-a)\) in \(S\) (2 remains unpaired), and note that each pair multiplies to a distinct value in \(S_1\). Due to claim \(2\), these values exactly cover the values of \(S_1\). Thus, \[\left(\prod_{a \in S_1} a \right) \cdot \left(\prod_{a \in S_2} a \right) = \left(\prod_{a \in S} a \right) = 2 \left(\prod_{a \in S_1} a \right),\] and as \(S_2\) is simply \(A\) under equivalence mod \(p\), we are done.

Beautiful solution, Dantaxyz!

The answer is that $\prod_{a \in A} a \equiv 2 \pmod p$ regardless of the value of $p$. Here is the official solution, where we always work in ${\mathbb F}_p$. We define \begin{align*} A &= \left\{ a \in {\mathbb F}_p \mid a, 4-a \text{ not qr} \right\} \\ B &= \left\{ b \in {\mathbb F}_p \mid b, 4-b \text{ qr}, b \ne 0, b \ne 4 \right\}. \end{align*}Note that $a \in A \iff 4-a \in A$ and $b \in B \iff 4-b \in B$. We now do the following magical calculation in ${\mathbb F}_p$: \begin{align*} \prod_{b \in B} b = \prod_{b \in B} (4-b) &= \prod_{\substack{1 \le y \le (p-1)/2 \\ y \ne 2 \\ 4-y^2 \text{ is qr}}} (4-y^2) \\ &= \prod_{\substack{1 \le y \le (p-1)/2 \\ y \ne 2 \\ 4-y^2 \text{ is qr}}} (2+y) \prod_{\substack{1 \le y \le (p-1)/2 \\ y \ne 2 \\ 4-y^2 \text{ is qr}}} (2-y) \\ &= \prod_{\substack{1 \le y \le (p-1)/2 \\ y \ne 2 \\ 4-y^2 \text{ is qr}}} (2+y) \prod_{\substack{(p+1)/2 \le y \le p-1 \\ y \ne p-2 \\ 4-y^2 \text{ is qr}}} (2+y) \\ &= \prod_{\substack{1 \le y \le p-1 \\ y \ne 2, p-2 \\ 4-y^2 \text{ is qr}}} (2+y) \\ &= \prod_{\substack{3 \le z \le p+1 \\ z \ne 4,p \\ z(4-z) \text{ is qr}}} z \\ &= \prod_{\substack{0 \le z \le p-1 \\ z \ne 0,4,2 \\ z(4-z) \text{ is qr}}} z. \end{align*}Note $z(4-z)$ is a nonzero quadratic residue if and only if $z \in A \cup B$. So the right-hand side is almost the product over $z \in A \cup B$, except it is missing the $z=2$ term. Adding it in gives \[ \prod_{b \in B} b = \frac{1}{2} \prod_{\substack{0 \le z \le p-1 \\ z \ne 0,4 \\ z(4-z) \text{ is qr}}} z = \frac{1}{2} \prod_{a \in A} a \prod_{b \in B} b. \]This gives $\prod_{a \in A} a = 2$ as desired.

oops this was basically just a detailed, extended explanation of mathisawesome2169's summary of sraphael's text message summary of his amazing solution Shoutout to MALLSTARS.

Why "Sad Number Theory"?

My solution: Notice $a\in A \Leftrightarrow 4-a \in A$, take $a=4b$ tell us to consider $$B=\left\{a: 1\leq a<p, \left(\frac{a}{p} \right)=\left(\frac{1-a}{p} \right)=-1\right\},$$then $\displaystyle\prod_{a\in A}a \equiv 4^{|A|}\prod_{a\in B}a$, $$|A|=\frac{1}{2}\sum_{k=1}^{\frac{p-1}{2}}\left(1-\left(\frac{4-g^{2k-1}}{p} \right)\right),$$where, $g$ satifies $\text{ord}_{p}(g)=p-1$. We know: \[ \sum_{j=1}^{\frac{p-1}{2}}(g^{n})^j \equiv \begin{cases} 0\pmod{p}, & \text{if $p-1 \nmid n$} \\ -\frac{1}{2}\pmod{p}, & \text{if $p-1 \mid n$} \end{cases}, \]then: \[ \sum_{k=1}^{\frac{p-1}{2}} \left(\frac{4-g^{2k-1}}{p} \right) \equiv \sum_{k=1}^{\frac{p-1}{2}}(4-g^{2k-1})^{\frac{p-1}{2}} =\sum_{l=0}^{\frac{p-1}{2}}C_{\frac{p-1}{2}}^l g^{-l}(-1)^l 4^{\frac{p-1}{2}-l}\sum_{k=1}^{\frac{p-1}{2}}(g^{2l})^k \equiv -\frac{1}{2}\sum_{\substack{0\leq l\leq \frac{p-1}{2}\\ p-1\mid 2l}} C_{\frac{p-1}{2}}^l g^{-l}(-1)^l 4^{\frac{p-1}{2}-l} =-\frac{1}{2}\left(1-(-1)^{\frac{p-1}{2}}\right) \pmod{p} \]So, $$|A|\equiv \frac{p-1}{4}+\frac{1}{4}\left(1-(-1)^{\frac{p-1}{2}}\right) \pmod{p},$$$|A|\leq \frac{p-1}{2}$, then $$|A|=\frac{p-1}{4}+\frac{1}{4}\left(1-(-1)^{\frac{p-1}{2}}\right)=\frac{p-(-1)^{\frac{p-1}{2}}}{4}.$$ we only need to work $\displaystyle\prod_{a\in B}a$, let $S=\left\{x: \left(\frac{x}{p}\right)=-1, x\in \mathbb{F}_p\right\}$, clearly $a\in B \Leftrightarrow 1-a \in B$, we have $$\prod_{a\in B}a\equiv \prod_{a\in B}(1-a)\pmod{p},$$then $$\prod_{a\in B}\left(\frac{1}{a}-1\right) \equiv 1\pmod{p}.$$Notice: for any $a\in B$, we have $\left(\frac{a}{p} \right)=\left(\frac{1-a}{p} \right)=-1$, so $$\left(\frac{\frac{1}{a}-1}{p} \right)=1,$$ Case1 If $p\equiv -1\pmod{4}$, for any $a\in B$, we have $$\left(\frac{1-\frac{1}{a}}{p} \right)=\left(\frac{\frac{1}{a}-1}{p} \right)=-1,$$it follows that $a\in B \Leftrightarrow a^{-1}\in B$. $(\frac{-1}{p})=-1$ tells us $$-1\in B \Leftrightarrow 2\in B \Leftrightarrow \left(\frac{2}{p} \right)=-1 \Leftrightarrow p\equiv 3\pmod{8},$$then, Case1.1 If $p\equiv 3\pmod{8}$, $-1\in B$, from $a\in B \Leftrightarrow a^{-1}\in B$, we get $$\prod_{a\in B}a\equiv -\prod_{a\in B\setminus \{-1\}}a\equiv -1\pmod{p}.$$ Case1.2 If $p\equiv 7\pmod{8}$, $-1\notin B$, $a\in B \Leftrightarrow a^{-1}\in B$, then $$\prod_{a\in B}a\equiv 1\pmod{p}.$$ now we have: \[ \prod_{a\in A}a \equiv \begin{cases} -4^{|A|} \pmod{p}, & p\equiv 3\pmod{8} \\ 4^{|A|} \pmod{p}, & p\equiv 7\pmod{8} \end{cases}. \] Case2 If$p\equiv 1\pmod{4}$, now, $\left(\frac{-1}{p}\right)=1$, then $$\left(\frac{1-\frac{1}{a}}{p} \right)=1,$$it follows that $a\in B \Leftrightarrow a^{-1}\notin B$, notice $$\prod_{a\in B}a\equiv \prod_{a\in B}(1-a)\pmod{p},$$then \[ \prod_{x\in S}(1-x)\equiv \prod_{a\in B}(1-a) \prod_{a\in S\setminus B}(1-a) \equiv \prod_{a\in B}(1-a) \prod_{a\in B}\left(1-\frac{1}{a}\right) \pmod{p} \equiv (-1)^{|A|}\prod_{a\in B}(1-a) \]we have $$\prod_{a\in B}a\equiv \prod_{a\in B}(1-a)\equiv (-1)^{|A|}\prod_{x\in S}(1-x),$$now we only need to do $\prod_{x\in S}(1-x)$. Notice: $$f(x)=\prod_{k\in S}(x-k)\equiv x^{\frac{p-1}{2}}+1\pmod{p},$$then, $$\prod_{x\in S}(1-x)=f(1)\equiv 2\pmod{p}.$$and, $$\prod_{a\in A}a\equiv (-1)^{|A|}2\cdot 4^{|A|}\pmod{p}.$$ Back to the problem: \[ \prod_{a\in A}a \equiv \begin{cases} -2^{\frac{p+1}{2}} \pmod{p}, & p\equiv 3\pmod{8} \\ 2^{\frac{p+1}{2}} \pmod{p}, & p\equiv 7\pmod{8} \\ (-1)^{|A|}2^{\frac{p+1}{2}} \pmod{p}, & p\equiv 1\pmod{4} \end{cases}. \]So, $$\prod_{a\in A}a \equiv 2\pmod{p}.$$

shalomrav wrote: Why "Sad Number Theory"? This is a sequel Reference: https://artofproblemsolving.com/community/q1h1823555p12189457

Very interesting and beautiful problem! Here is another way to arrive at pieater314159's generating function. Let $M$ denote the desired product. We claim that $M\equiv 2\pmod p$. Part 1: Eliminating the quadratic non-residue. The central claim of this section is the following. Claim: We have the following identity (in $\mathbb{F}_p[x]$) $$2\prod_{a\in A}(x-a)^2 = x^{\frac{p+1}{2}} + (4-x)^{\frac{p+1}{2}}+4$$Proof: Observe that both sides have equal leading coefficients. Moreover, by Euler's Criterion, each $a\in A$ is the root of RHS. Hence it suffices to show that each root has multiplicity $2$. To do that, we compute (denote by $F(x)$ the RHS) $$F'(a) = \frac{p+1}{2}\cdot a^{\frac{p-1}{2}} - \frac{p+1}{2}\cdot (4-a)^{\frac{p-1}{2}} \equiv 0 \pmod p$$thus each root has multiplicity $2$ as claimed.$\blacksquare$ At this point, note upon pluggin in $x=0$ that $M^2\equiv 4\pmod p$ thus the desired product is either $2$ or $-2$. When $p\equiv 3\pmod 4$, one can compute $|A| = \tfrac{p+1}{4}$. Thus $$\left(\frac Mp\right) = (-1)^{\frac{p+1}{4}} = \left(\frac 2p\right)$$Hence $M$ must be $2\pmod p$. Unfortunately, this does not work for $p\equiv 1\pmod 4$, which is a long way to go. Part 2: Eliminating the $\pmod p$ condition. First, we will transform the identity slightly. By plugging in $x\to\tfrac{1}{x}$, we find $$\prod_{a\in A}(1-ax)^2 = \frac{1+(4x-1)^{\frac{p+1}{2}}+4x^{\frac{p+1}{2}}}{2x}\qquad (*)$$Let $k=\tfrac{p+1}{2}$ and $f(x)^2$ denote the LHS above. By Binomial theorem, we find that \begin{align*} f(x)^2 &= \frac{1}{2x}\left(\binom{k}{1}4x - \binom{k}{2}(4x)^2 + \hdots + (-1)^{k+1}\binom{k}{k} (4x)^k + 4\cdot x^k\right) \\ &\equiv \frac{1}{2x}\left(\binom{\tfrac 12}{1}4x + \binom{\tfrac 12}{2}(4x)^2 + \hdots + (-1)^{k+1}\binom{\tfrac 12}{k}(4x)^k +4\cdot x^k\right) \pmod p \end{align*}This screams for generating function so that's what we will do. Define $$F(x) = \sqrt{\frac{1-\sqrt{1-4x}}{2x}}$$for $x$. Notice that $F(x)^2 \equiv f(x)^2 \pmod{p,x^{k-1}}$. Thus by repeatedly comparing coefficients in $\mathbb{F}_p$, we get that $F(x)\equiv f(x)\pmod{p,x^{\frac{k-1}{2}}}$. Thus it suffices to find the coefficients of $F$. Part 3: Generating functions time! We manipulate $F$ as follows \begin{align*} F(x) &= \frac{1}{\sqrt{4x}}\sqrt{2-2\sqrt{1-4x}} \\ &= \frac{1}{2\sqrt{x}}\left(\sqrt{1+2\sqrt{x}} - \sqrt{1-2\sqrt{x}}\right) \\ &= \binom{\tfrac 12}{1}\cdot 2 + \binom{\tfrac 12}{3}\cdot 8x + \binom{\tfrac 12}{5}\cdot 32x^2 + \hdots \end{align*}where the last step follows from generalized binomial theorem. Thus the coefficient of $x^{\tfrac{p-1}{4}}$ is (keep in mind that $k=\tfrac{p+1}{2}$) $$2^k\binom{\frac{1}{2}}{k} \equiv 2^k\binom{k}{k} \equiv 2\cdot\left(\frac{2}{p}\right)\pmod p$$Since when $p\equiv 1\pmod 4$, $\left(\tfrac 2p\right) = (-1)^{\frac{p-1}{4}}$, by comparing the coefficient of $x^k$ in $(*)$, we get the desired result.

Beautiful problem The solutions below are the result of a groupsolve with Aryan-23, RandomTraveller and MathPassionForever a few months back. We had two main ideas both of which lead to solutions. tastymath75025 wrote: Let $p$ be an odd prime. An integer $x$ is called a quadratic non-residue if $p$ does not divide $x-t^2$ for any integer $t$. Denote by $A$ the set of all integers $a$ such that $1\le a<p$, and both $a$ and $4-a$ are quadratic non-residues. Calculate the remainder when the product of the elements of $A$ is divided by $p$. Proof 1 (Mapping): We claim the answer is always $2$ irrespective of $p.$ Define the set $B=\{b:b,4-b \in \text{QR}\} \backslash \{0,4\}.$ We work in $\mathbb{F}_p,$ so that each equality below is actually a congruence mod $p.$ Define $X=(A \cup B) \backslash \{2\}.$ We start by establishing the following key claim: Claim: For any $b,$ $b \in B \iff b=x(4-x)$ for some $x \in X$ Proof: Clearly for $x \in X,$ $x(4-x)$ is a QR. Now suppose $b \in B.$ Then $$4-b=y^2 \iff b=4-y^2=(2-y)(2+y).$$So take $x=y+2.$ Then $x(4-x)$ is a QR and so $x \in X,$ and $b=x(4-x)$ so this works. $\square$ The claim gives us a natural mapping from $f:X \mapsto B$ given by $x \mapsto x(4-x),$ which is in $B.$ The key observation now is that $f(\alpha)=f(\beta) \iff \alpha =\beta$ or $\alpha+\beta = 4.$ Hence, for $x \ne 2,$ each pair $(x,4-x) \in X^2$ maps to a unique element of $B,$ and this covers all the elements of $B.$ Hence, $$2\prod_{b \in B} b=\left( \prod_{x \in X} x \right)=\left( \prod_{a \in A}a \right)\left( \prod_{b \in B} b \right) \implies \prod_{a \in A}a=2.$$ Proof 2 (Direct Calculation): Define $B$ as before. Then \begin{align*} \prod_{b \in B} b &= \prod_{4-b \in B} 4-b\\ &= \prod_{\substack{4-c^2 \in QR \\ 1 \le c \le \frac{p-1}{2} \\ c \ne 2}} 4-c^2 \\ &= \prod_{\substack{4-c^2 \in QR \\ 1 \le c \le \frac{p-1}{2} \\ c \ne 2}} (2+c)(2+c)\\ &= \prod_{\substack{4-c^2 \in QR \\ 1 \le c \le \frac{p-1}{2} \\ c \ne 2}} (2+c) \prod_{\substack{4-c^2 \in QR \\ \frac{p+1}{2} \le c \le p-1 \\ c \ne p-2}} (2+c)\\ &= \prod_{\substack{4-c^2 \in QR \\ 1 \le c \le p-1 \\ c \ne 2,-2}} (2+c)\\ &= \prod_{\substack{d(4-d) \in QR \\ 3 \le d \le p+1 \\ d \ne 0,4}} d\\ &= \prod_{\substack{d(4-d) \in QR \\ 1 \le d \le p-1 \\ d \ne 0,2,4}} d\\ &= \prod_{d \in A \cup B, d \ne 2} d. \end{align*}It is easy to see that this gives the result now. $\blacksquare$

Sad number theory indeed. The remainder is always $2$. Work in $F=\mathbb{Z}_p$. Let $A$ be the set of elements $a \in F$ such that $a,4-a$ are QNRs and $D$ be the set of elements $d\in F$ such that $d,4-d$ are QRs and $d\not\in\{0,4\}$. Note if $d\in D$, then we can let $d=t^2$ so $4-t^2=(2+t)(2-t)$ is a QR and thus $\{2+t,2-t\}\in D$ or $A$. This argument works because $t=0\implies 4-t=4$ is a QR. This argument works in reverse because $t\in D\implies t(4-t) = 4-(t-2)^2\in A$ and $t\in A\implies t(4-t)=4-(t-2)^2\in A$. Write \[\prod_{a\in D} (4-a) = \prod_{a\in D} (2-\sqrt{a})(2+\sqrt{a})=\frac{\prod_{2-t\in D}a \cdot \prod_{2-t\in A}a}{2}.\]The factor of $1/2$ appears because $2$ cannot appear in the product as $2+0,2-0$ are forbidden from appearing. Rearranging yields the desired.

We claim the answer is $\boxed{2}$. Let $R$ denote the complete residue class mod $p$ except for $0$. Note that the bijection $a \to 4a$ makes things a bit easier, because it lets us rewrite the condition as both $a, 1 - a$ are both QNR's, which is an easier condition to work with. All operations are taken mod $p$. Consider the case where $\left(a | p\right), \left(1 - a | p\right)$ are of opposite sign. Then $$\left(\dfrac{a}{p}\right)\left(\dfrac{1 - a}{p}\right) = -1 = \left(\dfrac{a - a^2}{p}\right) = \left(\dfrac{1/a - 1}{p}\right)\left(\dfrac{a^{-2}}{p}\right) = \left(\dfrac{-1}{p}\right)\left(\dfrac{1 - 1/a}{p}\right)$$so there's a possible relationship between the signs of $\{\left(a | p\right), \left(1 - a | p\right)\}$ and $\{\left(a^{-1} | p\right), \left(1 - a^{-1} | p\right)\}$. Splitting up the residues $a$ based on whether $1 - a$ is a QR or not, we let $A$ denote the set of all integers $a \in R$ such that $a, 1 - a$ are both QNRs, $A_1$ the set of all integers $a \in R$ such that $a$ is a QR but $1 - a$ is an NQR, and $A_2$ the set of all integers $a \in R$ such that $1 - a$ is an NQR. Then we have $$\prod_{a \in A_2} a = \left(\prod_{a \in A}a\right)\left(\prod_{a \in A_1}a\right)$$which will give us a way to calculate the product in $A$. However, finding $A_2$ is hard, so let $A_3$ be the set of all integers $a \in R$ such that $1 - a$ is a QR, or, $1 - a = x^2 \iff a = 1 - x^2$, where $2 \leq x^2 \leq (p - 1)/2$ (if $x = 1$ then $a = 0 \not\in R$). Now by Wilson's Theorem $$-1 = \prod_{a \in R}a = \left(\prod_{a \in A_2}a\right)\left(\prod_{a \in A_3}a\right)$$and \begin{align*} \prod_{a \in A_3}a &= \prod_{x = 2}^{(p - 1)/2} \left(1 - x^2\right) = \prod_{x = 2}^{(p - 1)/2} (1 + x)(1 - x) \\ &= \prod_{x = 3}^{p - 1}x = 2^{-1} \\ \prod_{a \in A_2}a &= -2. \end{align*} Case 1: -1 is a QR mod p. This implies $p \equiv 1 \pmod{4}$, and also implies that if $a \in A_1$ then $a^{-1} \in A_1$ too. The one edge case to take notice of is the case of $a = -1$, since $-1$ is its own inverse; whether $-1 \in A_1$ is dependent on if $2$ is a QR or not; if $2$ is a QR then $-1 \not\in A_1$ and so the product is $1$, but if $2$ is NQR then $-1 \in A_1$ and so the product is $1$. In other words, $$\prod_{a \in A_1} = \left(\dfrac{2}{p}\right).$$ Case 2: -1 is NQR mod p. This implies $p \equiv 3 \pmod{4}$ and is actually a one-liner: $$a \in A \iff \left(\dfrac{a}{p}\right)\left(\dfrac{1 - a}{p}\right) = 1 = \left(\dfrac{a - a^2}{p}\right) = -\left(\dfrac{1 - 1/a}{p}\right) \iff a^{-1} \in A \iff \prod_{a \in A}a = \left(\dfrac{2}{p}\right)$$ However, $2\left(2 | p\right)^{-1}$ isn't always $2$, what's going on here? The original problem's condition was $a, 4 - a$ both NQRs, not $a, 1- a$ so we need to account for our map $a \to 4a$ by correcting by $4^{|A|}$. We find $|A|$ as follows: \begin{align*} |A| &= \dfrac{1}{4} \sum_{a \in R}\left[1 - \left(\dfrac{a}{p}\right)\right]\left[1 - \left(\dfrac{1 - a}{p}\right)\right] = \dfrac{1}{4}\sum_{a \in R} 1 - \left(\dfrac{a}{p}\right) - \left(\dfrac{1 - a}{p}\right) + \left(\dfrac{a - a^2}{p}\right) \\ &= \dfrac{1}{4}\left[p + \sum_{a \in R} \left(\dfrac{1/a - 1}{p}\right)\right] = \dfrac{1}{4}\left[p + \sum_{a \in R, a \neq -1} \left(\dfrac{a}{p}\right)\right] \\ &= \dfrac{p - (-1)^{(p - 1)/2}}{4} \end{align*}so if $p = 4k \pm 1$ then $|A| = k$. If $p = 4k + 1$ then $4^k = 2^{2k} = 2^{(p - 1)/2} = \left(2 | p\right)$ and so our answer is $2$; similarly if $p = 4k - 1$ then $4^k = 2^{2k} = 2 \cdot 2^{(p - 1)/2} = 2 \left(2 | p\right)$ and likewise our answer is $2$.

Very elegant problem! Solved with bora_olmez. The answer is that the product is always equal to $2$ Let $B$ denote the set of numbers $b$ such that both $b$ and $4-b$ are quadratic residues and let $S$ denote the set of numbers $s$ such that $s(4-s)$ is a perfect square. We will ignore every occurence of $0,2,4$ in the sets $A,B,S$. Note that $S = A \cup B$ Note that if $b \in B$ such that $b = k^2$, then $4-b = 4 - k^2 = (2+k)(2-k)$ and therefore, $2+k, 2-k \in S$. This means every element in $B$ can be written as $b = x(4-x)$ for some $x \in S$ and this is injective except for $b,4-b$ things. Also note that every number $s$ in $S$ has a pair, $4-s$ also in $S$. Finally, also observe that $a \in A \implies a(4-a) \in B$ since $a(4-a)$ is a QR and $4 - a(4-a) = 4 - 4a + a^2 = (a-2)^2$ We're basically ready to finish now. Consider the product of every number in $S$. This is basically the product of $x(4-x)$ across every pair (we can pair things since we excluded $2$). However, on the other hand, since $S = A \cup B$, its the product of elements in $A$ (call this $X$) times the elements in $B$ (call this $Y$) Observe that $Y$, is just product of everything in $B$, which is again just every number of the form $x(4-x)$ by our previous observations. Also none of these numbers are zero because we excluded $0$ and $4$. Therefore, we can just cancel these terms so we obtain $X = 1$. But initially we excluded $2$ also, so adding it back (see it always appears on the other side as that of $X$), we obtain $X = 2$ always!, so we are done. $\blacksquare$

Solved with rama1728. Let $X$ be the set of residues $a$ where $a(4-a)$ is a QR and neither $a$ nor $4-a$ equal $0$ or $4.$ Let $B$ be the set of residues $a$ where $a$ and $4-a$ are QRs and neither $a$ nor $4-a$ equal $0$ or $4.$ Note that $A \cup B = X.$ So $$\prod_{a \in X}a \equiv \prod_{a \in A} a \prod_{a \in B} a \pmod{p}$$and since both sides are nonzero, it suffices to show $$\prod_{a \in X}a \equiv 2 \prod_{a \in B}a \pmod{p}.$$For any $a \in X,$ we have $a(4-a)$ and $(a-2)^2$ being QRs, and $a(4-a) + (a-2)^2 \equiv 4 \pmod{p}.$ So unless $a = 2,$ $a(4-a) \in B.$ Also, for any residue $k \in b,$ there are only at most two roots to $a(4-a) \equiv k \pmod{p}.$ We pair up elements in $X$ summing to $4$ in our product, leaving $2$ unpaired. There are $\frac{|X|-1}{2}$ of these pairs, and each of these pairs multiplies to a different element in $B,$ thus $|B| \ge \frac{|X|-1}{2}.$ It suffices to show that all elements of $B$ are accounted for, in other words $\frac{|X|-1}{2} \ge |B|.$ To do this, note that for any $a \in B,$ we have that $a \equiv k^2 \pmod{p}$ for some $k$ and $4-a \equiv 4-k^2 \equiv(2+k)(2-k)$ is a quadratic residue, meaning $2+k,2-k \in B.$ So we can generate $2|B|$ distinct elements of $|X| \setminus \{2\}$ as desired since $2 \pm k \equiv 2 \pm l \implies k^2 \equiv l^2 \pmod{p}.$ $\blacksquare$

Work in $\mathbb F_p$. Note that \[ A = \left\{ a \; \left| \; \left( \frac ap \right) = -1 \quad \text{and} \quad \left( \frac {4-a}p \right) = -1 \right.\right\}.\]Let \[ B = \left\{ b \; \left| \; \left( \frac bp \right) = 1 \quad \text{and} \quad \left( \frac {4-b}p \right) = 1 \right.\right\}.\]Note that if $x \in A \cup B$, then \[ 1 = \left( \frac xp \right) \left( \frac {4-x}p \right) = \left( \frac{4x-x^2}p \right) = \left( \frac{4-(x-2)^2}p \right),\]hence $(x-2)^2 \in B$ or $(x-2)^2 = 0$ (i.e. $x=2$). Moreover, $\left( \frac xp \right) \left( \frac {4-x}p \right) = 1$ iff $x \in A \cup B$, so all the above steps are reversible, hence all such $x \in A \cup B$ are of the form $2 \pm \sqrt{b}$ for some $b \in B$ or $2$. Thus (since $A$ and $B$ are obviously disjoint), \[ \prod_{a \in A} a = \frac{\prod\limits_{x \in A \cup B} x}{\prod\limits_{b \in B} b} = 2 \cdot \prod_{b \in B} \frac{(2 + \sqrt{b})(2 - \sqrt{b})}{b} = 2 \cdot \prod_{b \in B} \frac{4-b}{b} = 2,\]since $b \in B$ iff $4-b \in B$, and we are done. $\blacksquare$

Cool problem with a short and clean solution. Let $B=\{n|0<n<p,\left(\frac{n}{p}\right)=\left(\frac{4-n}{p}\right)=1\}$. Note that there are equally many QR's and QNR's mod $p$ excluding zero, so $|A|=|B|$ since the sizes of their complements in the sets of QR's and QNR's, respectively, are equal. Claim: for all $x\in A\cup B\setminus\{4\}$, we have $x(4-x)\in B$. Proof: Note that $\left(\frac{x(4-x)}{p}\right)=(\pm 1)^2=1$. Also, $x(4-x)=4-(x-2)^2$. Let $f(S)$ denote the product of all elements in set $S$. Note that by the equality of their size, each element in $B$, excluding $4$, is a product of some two mutually distinct elements in $A\cup B$, excluding $2$ and $4$. Therefore, we have $$\frac{f(A)f(B)}{8}=\frac{f(B)}{4}\rightarrow \boxed{f(A)=2}$$ Remark: by a similar argument, we can calculate that the product of all QR's outside $B$ is $1$. Hence, $f(B)$ is equal to $-1$ for $p$ 1 mod 4, and $1$ for $p$ 3 mod 4.

We claim the answer is $\boxed{2}$. Let a quadratic residue be a Q and a non-quadratic residue an N. Let the product of the elements in a set $X$ be $P(X)$. We make extensive use of the fact that Legendre symbols are completely multiplicative. Part 1: Conversion to $a', a'-1$. $\left(\frac{4^{-1}}{p}\right) = 1$ as $4^{-1} \equiv (2^{-1})^2 \pmod{p}$. Hence, $(a, 4-a)$ are $(N, N) \iff (4^{-1}a, 1-4^{-1}a)$ are $(N, N)$. Let $a' = 4^{-1}a$. Let $A'$ be the set of all residuals $a'$ such that $a', 1-a'$ are both $N$. Note that by the transformation above, $A' = 4^{-1}A$. Hence, it suffices to show that $P(A') \equiv (4^{-1})^{|A|} \cdot 2 \equiv 2^{1 - 2|A|} \pmod{p}$. Let $NQ$ denote the set of residuals $a$ such that $a$ is $N$ and $a-1$ is $Q$. Similarly define $NN, QN, QQ$. If $p \equiv 1 \pmod{4}$, $\left(\frac{-1}{p}\right) = 1$. Thus, $a', 1-a'$ both $N \iff a', a'-1$ both $N$, i.e. $a' \in NN$. It suffices to find $P(NN)$. If $p \equiv 3 \pmod{4}$, $\left(\frac{-1}{p}\right) = -1$. Thus, $a', 1-a'$ both $N \iff a'$ is $N$ and $a'-1$ is $Q$, i.e. $a' \in NQ$. It suffices to find $P(NQ)$. Part 2: Assume $p \equiv 3 \pmod{4}$. Claim 2.1: $a \in NQ \iff a^{-1} \in NQ$. Proof: $a \in NQ \iff \left(\frac{a}{p}\right) = -1, \left(\frac{a-1}{p}\right) = 1$. $\left(\frac{a}{p}\right) \left(\frac{a^{-1}}{p}\right) = \left(\frac{1}{p}\right) = 1$, so $\left(\frac{a^{-1}}{p}\right) = -1$. Furthermore, $\left(\frac{a^{-1}-1}{p}\right) = \left(\frac{(1-a)a^{-1}}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac{a-1}{p}\right) \left(\frac{a^{-1}}{p}\right) = (-1) \cdot 1 \cdot (-1) = 1$. Thus, $a^{-1}$ is $N$, $a^{-1}-1$ is $Q$. $\square$ Claim 2.2: $P(NQ) \equiv \left(\frac{2}{p}\right) \pmod{p}$. Proof: $a, a^{-1}$ are distinct unless $a^2 \equiv 1 \pmod{p} \iff a \equiv \pm 1 \pmod{p}$. $1 \not \in NQ$ as $1$ is $Q$. $-1 \in NQ \iff -2$ is a $Q \iff 2$ is a $N$, or $\left(\frac{2}{p}\right) = -1$. If $-1 \in NQ$, then $P(NQ)$ consists of $a \cdot a^{-1}$ for distinct $a, a^{-1}$ apart from $a \equiv -1$. Hence, $P(NQ) \equiv -1 \pmod{p}$. If $-1 \not \in NQ$, then $P(NQ)$ only consists of pairs of distinct $a, a^{-1}$, so $P(NQ) \equiv 1 \pmod{p}$. Now, note that this can be represented as $P(NQ) \equiv \left(\frac{2}{p}\right) \pmod{p}$. $\square$ It suffices to prove that $2^{1-2|A|} \equiv \left(\frac{2}{p}\right) \pmod{p}$. Claim 2.3: $|A| = \frac{p+1}{4}$. Proof: It's well-known that $|Q| = |N| = \frac{p-1}{2}$. Similar to Claim 2.1 above, we find that $a \in QQ \iff a^{-1} \in QN$. Note that 1 is excluded from $QQ$. Thus, $|QQ| = |QN| = \frac{\frac{p-1}{2}-1}{2} = \frac{p-3}{4}$. By another similar calculation, this time using $1 - a^{-1} = \frac{a-1}{a}$, we find that $a \in NN \iff 1 - a^{-1} \in QQ$. Thus, $|NN| = |QQ| = \frac{p-3}{4}$. Now $|NQ| = |N| - |NN| = \frac{p+1}{4}$. $\square$ Now note that $2^{1-2|A|} \equiv 2^{1-\frac{p+1}{2}} \equiv 2^{\frac{1-p}{2}} \equiv (2^{\frac{p-1}{2}})^{-1} \equiv \left(\frac{2}{p}\right)^{-1} \equiv \left(\frac{2}{p}\right) \pmod{p}$ where we've used Euler's criterion and the fact that $\left(\frac{2}{p}\right) \in \{-1, 1\}$. Part 3: Assume $p \equiv 1 \pmod{4}$. By a similar argument to Claim 2.1, we find that $a \in QN \iff a^{-1} \in QN$, and $P(QN) \equiv \left(\frac{2}{p}\right) \pmod{p}$. Furthermore, we find that $a \in NN \iff a^{-1} \in NQ$, so $|NN| = |NQ| = \frac{p-1}{4}$. It now suffices to show that $P(NN) \equiv 2^{1-2|A|} \equiv 2^{1 - \frac{p-1}{2}} \equiv 2 \left(\frac{2}{p}\right)$. Let $XN = NN \cup QN$, the set of residuals $a$ where $a-1$ is a $N$. It suffices to prove that $P(XN) \equiv 2 \cdot \left(\frac{2}{p}\right)^2 \equiv 2 \pmod{p}$. Claim 3.1: $P(XN) \equiv 2 \pmod{p}$. Proof: There exists a primitive root $g$ mod every prime. $g^2, g^4, ..., g^{p-1}$ form $\frac{p-1}{2}$ distinct quadratic residues (if not distinct, then $ord_p(g) < p-1$ contradiction) hence form the set $Q$. Thus, $g^1, g^3, ..., g^{p-2}$ form the $\frac{p-1}{2}$ distinct non-quadratic residues, i.e. $N = \{g^1, ..., g^{p-2}\}$. It suffices to prove that: \begin{align*} \prod_{a \in N} (a+1) \equiv 2 \pmod{p} \iff V = \prod_{i = 1}^{\frac{p-1}{2}} (g^{2i-1} + 1) \equiv 2 \pmod{p}. \end{align*} Let $\sigma_0, \sigma_1, ..., \sigma_{\frac{p-1}{2}}$ denote the elementary symmetric polynomials in $N$, with e.g. $\sigma_2 = g^1g^3 + ... + g^1g^{p-2} + ... + g^{p-4}g^{p-2}$ and $\sigma_0 = 1$. Let $S_0, S_1, ..., S_{\frac{p-1}{2}}$ denote the sums of powers of $N$, with e.g. $S_2 = (g^1)^2 + (g^3)^2 + ... + (g^{p-2})^2$ and $S_0 = 1 + 1 + ... + 1 = \frac{p-1}{2}$. Note that by Vieta's formulae, \begin{align*} V = \sum_{i = 0}^{\frac{p-1}{2}} \sigma_i. \end{align*} We prove by strong induction that $\sigma_{n} \equiv 0 \pmod{p}$ for $n = 1, 2, ..., \frac{p-1}{2}-1$. Base case: $n = 1$. As a geometric series, $\sigma_1 = g^1 + g^3 + ... + g^{p-2} = \frac{g(g^{p-1}-1)}{g^2-1} \equiv 0 \pmod{p}$, where we used $g^{p-1} - 1 \equiv 0 \pmod{p}$. Inductive step: Assume holds for all $k < n$. Noting that $n < \frac{p-1}{2} \Rightarrow 2n < p-1$, by Newton's identities, \begin{align*} S_n &= \sum_{i = 1}^{n} (-1)^{i+1}S_{n-i}\sigma_i \\ \Rightarrow (g^1)^n + (g^3)^n + ... + (g^{p-2})^n &= \sum_{i = 1}^{n-1} (-1)^{i+1}S_{n-i}\sigma_i \pm S_0\sigma_{n} \\ \Rightarrow \frac{g^n(g^{(p-1)n}-1)}{g^{2n}-1} &\equiv 0 \pm \frac{p-1}{2} \sigma_n \pmod{p} \\ \Rightarrow 0 &\equiv \pm \frac{p-1}{2} \sigma_n \pmod{p} \\ \Rightarrow \sigma_n &\equiv 0 \pmod{p}. \end{align*} Finally, we have $V \equiv \prod_{i = 1}^{\frac{p-1}{2}} g^{2i-1} + 1 \equiv g^{1 + 3 + ... + (p-2)} + 1 \equiv g^{\frac{p-1}{2}^2} + 1 \equiv (g^{\frac{p-1}{2}})^{\frac{p-1}{2}} + 1 \equiv (-1)^{\frac{p-1}{2}} + 1$. Since $\frac{p-1}{2}$ is even, $V \equiv 2 \pmod{p}$. $\square$

Let $A$ be the set of residues $r$ for which $r, 4 - r$ are both QR and $B$ be the set for which both are NQR. Note that $A, B$ are disjoint, and that if $r \in T = A \cup B$ then $r(4-r)$ is QR and $4 - r(4-r) = (2-r)^2$ is also QR. This is, unless $r = 0, 2, 4$ but we dont have to worry about $0$ or $4$ because they are guaranteed QRs. We will worry about $2$ later. Note that upon computing\[\prod_{r \in T} r\]we can pair $r, 4-r$ to always get QRs. These pairings must produce distinct QRs, since if we assume otherwise that $r \neq r', 4 - r \neq r'$ and $r(4-r) = r'(4 - r') \pmod p$ then $r + r' \equiv 4 \pmod p$. Now, since $2$ does not get paired, note that we arrive at $\tfrac12(|T| - 1)$ distinct QRs. I also claim these pairs cover all QRs. Otherwise, we have $|A| > \tfrac12(|T| - 1)$. However, every element $r \in T$ produces a QR $(r - 2)^2 \in A$, which can only by at most two values in $A$ (i.e $(r - 2)^2 \equiv (r' - 2)^2 \implies r = r', r + r' = 4$). Hence, in this manner, $\tfrac12(|T| - 1)$ QRs produced in this manner are $\geq |A|$, our desired contradiction. Hence, in\[\prod_{r \in T} r\]upon pairing $r, 4 - r$ and omitting $2$, we actually arrive at the product\[2\left(\prod_{r \in A} r\right) = \left(\prod_{r \in A} r\right)\left(\prod_{r \in B} r\right)\]giving our desired answer of\[\left(\prod_{r \in B} r\right) = 2\]and we are done.

Using the Legendre notation as usual, and working in $\mathbb{Z}/p\mathbb{Z}$, let $S$ be the set of residue classes $a$ modulo $p$ such that $$\left(\frac{a(4-a)}p\right)=1,$$so that, in particular, $a\notin\{0,4\}.$ Then, we can pair each $a\in S$ with a corresponding $a'\in S$ such that $a'\equiv4-a\pmod{p}$, each with the same value of \begin{align*} aa'&\equiv a(4-a)\pmod{p}\\ &\equiv4-(a-2)^2\pmod{p}. \end{align*}Since $a\not\equiv a'\pmod{p}$ for $a\neq2$ and \begin{align*} (a-2)+(a'-2)&\equiv(a-2)+(2-a)\pmod{p}\\ &\equiv0\pmod{p}, \end{align*}we deduce that exactly one element in the set $\{a-2,a'-2\}$ is in the range $\{1,2,\cdots,\frac{p-1}2\}$. Therefore, ranging across all possible values of $a\in S$, where $a\neq2$ and $a\le\frac{p-1}2$, and multiplying together all values of $aa'\equiv4-(a-2)^2\pmod{p}$, will yield the product of all $a\in S$ such that $a\neq a'$, or equivalently $a\neq2.$ Hence, it then follows that $\prod_{a\in S}a$ is just double the previously described product, and we find that $$\prod_{a\in S}a\equiv2\left(\prod_{\substack{a\in S\backslash\{2\},\\a\le\frac{p-1}2}}(4-(a-2)^2)\right)\pmod{p}.$$ Continuing, let us define $b=(a-2)^2$, so that both $b$ and $4-b\equiv 4-(a-2)^2\equiv a(4-a)\pmod{p}$ are quadratic residues. Note that $b\equiv(a-2)^2\pmod{p}$ can take on any nonzero value modulo $p$, so there is no restriction on the modulo $p$ residue of $b$. It therefore follows that \begin{align*} \prod_{a\in S}a&\equiv2\left(\prod_{\substack{a\in S\backslash\{2\},\\a\le\frac{p-1}2}}(4-(a-2)^2)\right)\pmod{p}\\ &\equiv2\left(\prod_{\substack{\left(\frac{b}p\right)=\left(\frac{4-b}p\right)=1,\\b\notin\{0,4\}}}(4-b)\right)\pmod{p}. \end{align*} Now, if $a\in S$, then \begin{align*} \left(\frac{a}{p}\right)\left(\frac{4-a}{p}\right)&=\left(\frac{a(4-a)}p\right)\\ &=1, \end{align*}so it follows $\left(\frac{a}{p}\right)$ and $\left(\frac{4-a}{p}\right)$ have the same sign, implying that $a$ and $4-a$ are either both quadratic residues or both quadratic nonresidues modulo $p$. Thus, we can rewrite the previously derived product equation as $$\left(\prod_{\substack{\left(\frac{a}p\right)=\left(\frac{4-a}p\right)=1,\\a\notin\{0,4\}}}a\right)\left(\prod_{\substack{\left(\frac{a}p\right)=\left(\frac{4-a}p\right)=-1,\\a\notin\{0,4\}}}a\right)\equiv2\left(\prod_{\substack{\left(\frac{b}p\right)=\left(\frac{4-b}p\right)=1,\\b\notin\{0,4\}}}(4-b)\right)\pmod{p}.$$Noting that the first product on the left hand side and the product on the right hand side are exactly the same, it follows that $$\prod_{\substack{\left(\frac{a}p\right)=\left(\frac{4-a}p\right)=-1,\\a\notin\{0,4\}}}a\equiv2\pmod{p}.$$Since $0$ and $4$ are not in $A$, the above product is exactly the product of all elements in $A.$ Therefore, we get that \begin{align*} \prod_{a\in A}a&\equiv\prod_{\substack{\left(\frac{a}p\right)=\left(\frac{4-a}p\right)=-1,\\a\notin\{0,4\}}}a\pmod{p}\\ &\equiv2\pmod{p}, \end{align*}so we are done. $\blacksquare$ - Jörg

Work entirely in $\mathbb F_p$, let $B$ the set of numbers $b \ne 0,4$ such that $b,4-b$ are QRs $\pmod p$. $$\prod_{b \in B} b=\prod_{\substack{x \ne 2 \\ 4-x^2 \; \text{QR} \\ 1 \le x \le \frac{p-1}{2}}} (4-x^2)=\prod_{\substack{x \ne 2 \\ 4-x^2 \; \text{QR} \\ 1 \le x \le \frac{p-1}{2}}} (2+x) \cdot \prod_{\substack{x \ne 2 \\ 4-x^2 \; \text{QR} \\ 1 \le x \le \frac{p-1}{2}}} (2-x)=\prod_{\substack{x \ne 2 \\ 4-x^2 \; \text{QR} \\ 1 \le x \le \frac{p-1}{2}}} (2+x) \cdot \prod_{\substack{x \ne p-2 \\ 4-x^2 \; \text{QR} \\ \frac{p+1}{2} \le x \le p-1}} (2+x)=\prod_{\substack{x \ne 2,p-2 \\ 4-x^2 \; \text{QR} \\ 1 \le x \le p-1}} (2+x)=\prod_{\substack{t \ne 0,2,4 \\ t(4-t) \; \text{QR} \\ 0 \le t \le p-1}} t$$Now note that any such $t$ lies in $A \cup B$, now we have to add the $2$ which is missing in the product and we get: $$2 \cdot \prod_{b \in B} b =\prod_{t \in A \cup B} t=\prod_{b \in B} b \cdot \prod_{a \in A} a \implies \prod_{a \in A} a=2$$Therefore the desired product is $2 \pmod p$ thus we are done .