JustSolveItAndSleep

Basically the same as USA TST 2010/9.

Use the Legendre symbol. We have $$\sum_{x\in\mathbb{F}_p}\left(\frac{x^5+x}{p}\right)\equiv\sum_{x=0}^{p-1}\left(x^5+x\right)^{\frac{p-1}{2}}\equiv-2\binom{4k}{k}\pmod{p}.$$ Denote $f(x)=\left(\frac{x^5+x}{p}\right)$, then $f(x)=f(ix)=f(-x)=f(-ix)$, where $i^2\equiv -1\pmod{p}$. So $\sum_{x\in\mathbb{F}_p}f(x)=4\sum_{x^{2k}=1}f(x)=4\left(\sum_{x^{2k}=1, f(x)=1}1-\sum_{x^{2k}=1, f(x)=-1}1\right)$. Since there are 5 solutions $x$ such that $(x^4+1)x\equiv 0$ (by $p\equiv 1\pmod{8}$, $x^4\equiv 1$ has 4 solutions), we have $\sum_{x\in\mathbb{F}_p}f(x)\equiv 4(2k-1)\equiv 4\pmod{8}$. Suppose it's $8t+4$. Since $-8k<\sum_{x\in\mathbb{F}_p}f(x)<8k$ and $8t+4\equiv-2\binom{4k}{k}\pmod{p}$, we have $r=p-4t-2$ or $-4t-2$. All the possible values of $r$ are $2$ or $3$ modulo $4$, not perfect squares. Done.

This was my problem. I was a bit terrified to see it paired with my shortlist A7 on the same quiz Let $\left( \frac{\bullet}{p} \right)$ denote the Legendre symbol. We consider the two integers \[ M = \sum_{x=1}^{p-1} \left( \frac{1+x^4}{p} \right) \qquad\text{and}\qquad N = \sum_{x=1}^{p-1} \left( \frac{1+x^8}{p} \right). \]Notice that $M$ and $N$ are integers with $|M|, |N| < p$. Also, we contend $M \equiv 4 \pmod 8$ and $N \equiv 0 \pmod 8$. For the sum $M$, there are exactly four residues $x$ with $x^4=-1$, and the remaining residues make $2k-1$ groups of four contributing $\pm 4$ to the sum. Similarly, in the sum $N$ we have groups of eight contributing $0$ or $\pm 8$. On the other hand modulo $p$ we have \[ M \equiv \sum_{x=1}^{p-1} (1+x^4)^{4k} \equiv (p-1)\left( 2 + \binom{4k}{2k} \right) \pmod p \]and \[ N \equiv \sum_{x=1}^{p-1} (1+x^8)^{4k} \equiv (p-1)\left( 2 + 2\binom{4k}{k} + \binom{4k}{2k} \right) \pmod p. \]whence \[ \frac{M-N}{2} \equiv \binom{4k}{k} \pmod p. \]Note that $\frac{M-N}{2} \equiv 2 \pmod 4$ and lies in $(-p,p)$, hence \[ \frac{M-N}{2} \in \left\{ \pm 2, \pm 6, \dots, \pm (p-3) \right\}. \]Consequently $r \in \{2,3,6,7,10,11,\dots,p-3,p-2\}$. In particular, since squares are $0$ or $1$ mod $4$, it follows $r$ is not a square. Remark: It is still possible that $r$ is a quadratic residue modulo $p$; for example, $\binom{36}{9} \equiv 71 \equiv 12^2 \pmod{73}$.

As remarked before, this is similar to USA TST 2010/9. Work in $\mathbb F_p$. Observe that \[1+8\sum_{x\ne 0, x^k=1}\left(\frac{1+x}{p}\right) = 1+\sum_{x\ne 0}(1+x^8)^{4k} = \sum_x (1+x^8)^{4k}=\sum_i \binom{4k}{i}\sum_xx^{8i} = -2\binom{4k}{k}-\binom{4k}{2k}-1\]and \[1+4\sum_{x\ne 0, x^{2k}=1}\left(\frac{1+x}{p}\right) = 1+\sum_{x\ne 0}(1+x^4)^{4k} = \sum_x (1+x^4)^{4k}=\sum_i \binom{4k}{i}\sum_xx^{4i} = -\binom{4k}{2k}-1.\]Thus \[\frac{\binom{4k}{k}}{2} \equiv \sum_{x\ne 0, x^k = -1}\left(\frac{1+x}{p}\right) - \sum_{x\ne 0, x^k=1}\left(\frac{1+x}{p}\right)\pmod p.\]Note this sum is composed of $2k-1$ instances of $\pm 1$ and one instance of $0$, as $(-1)^{2k} = 1$, so the final sum is certainly odd: let it be $g$ with $|g|\le 2k-1$. If $g$ is positive, we are done as $2g$ cannot be a perfect square. Otherwise, we are done because $8k+1+2g\equiv -1\pmod 4$ is not a perfect square.

Let $g$ be the primitive root modulo $p$. Define \[K(a)=\sum_{x\in\mathbb{F}_p}\left(\frac{x^5+ax}{p}\right),\]then \[K(a)\equiv\sum_{x\in\mathbb{F}_p}(x^5+ax)^{4k}\equiv -\binom{4k}{k}(a^{3k}+a^k)\pmod{p},\]where we use the well-known fact \[\sum_{x\in\mathbb{F}_p} x^n\equiv\begin{cases} -1 & \text{, if } p-1|n\neq 0 \\ 0 & \text{, otherwise.} \end{cases}\]In particular, we have \[K(1)\equiv -2r\not\equiv 0\pmod{p},\quad K(g)\equiv -rg^{k}(g^{2k}+1)\not\equiv 0 \pmod{p},\quad K(g^2)\equiv -rg^{2k}(g^{4k}+1)\equiv 0 \pmod{p}\]since the numerator of $\binom{4k}{k}$ is not divided by $p$ and $g$ has order $8k$. Since $|K(g^2)|\leq p-1$, we have $K(g^2)=0$. Notice that \[K(at^4)=\sum_{x\in\mathbb{F}_p}\left(\frac{(tx)^5+at^4(tx)}{p}\right)=\left(\frac{t}{p}\right)K(a).\]That is $K(a)^2$ only depends on the class of $\mathbb{F}_p^\times/(\mathbb{F}_p^\times)^4\simeq\langle g\rangle/\langle g^4\rangle$. We can calculate that \begin{align*} \sum_{a\in\mathbb{F}_p} K(a)^2 & =\sum_{x\in\mathbb{F}_p}\sum_{y\in\mathbb{F}_p}\left(\frac{xy}{p}\right)\sum_{a\in\mathbb{F}_p}\left(\frac{(a+x^4)(a+y^4)}{p}\right) \\ & =\sum_{x\in\mathbb{F}_p^\times}\left(\sum_{y\in\mathbb{F}_p^\times,y^4\neq x^4}-\left(\frac{xy}{p}\right)+\sum_{y^4=x^4}(p-1)\left(\frac{xy}{p}\right)\right) \\ & =\sum_{x\in\mathbb{F}_p^\times}\left(p\sum_{i=0}^3\left(\frac{x^2g^{2ik}}{p}\right)-\sum_{x\in\mathbb{F}_p}\left(\frac{xy}{p}\right)\right) \\ & =4p(p-1), \end{align*}where we use the well-known fact that \[\sum_{x\in\mathbb{F}_p}\left(\frac{ax^2+bx+c}{p}\right)=\begin{cases} -\left(\frac{a}{p}\right) & \text{, if } p\nmid b^2-4ac \\ (p-1)\left(\frac{a}{p}\right) & \text{, if } p\mid b^2-4ac. \\ \end{cases}\]By above observation and $K(a)=0$, \[\sum_{a\in\mathbb{F}_p}K(a)^2=\frac{p-1}{4}\sum_{i=0}^3 K(g^i)^2,\]we conclude that \[K(1)^2+K(g)^2+K(g^3)^2=16p.\]Moreover, for $t\notin\mathbb{F}_p^\times$. By a similar calculation, we have \[ \sum_{a\in\mathbb{F}_p}K(a)K(at)=\sum_{x,y\in\mathbb{F}_p^\times}\left(\frac{xy}{p}\right)\sum_{a\in\mathbb{F}_p}\left(\frac{(x^4+a)(y^4+at)}{p}\right)=\sum_{x,y\in\mathbb{F}_p^\times}-\left(\frac{xyt}{p}\right)=0, \]since $-x^4\equiv -t^{-1}y^4\pmod{p}$ is impossible. Substitute $t=g$ and rewrite the LHS to \[\sum_{i=0}^3\sum_{\ell=0}^{2k-1}K(g^{4\ell+i})K(g^{4\ell+i+1})=\sum_{\ell=0}^{2k-1}\sum_{i=0}^3\left(\frac{g^{\ell}}{p}\right)^2K(g^{i})K(g^{i+1})=2k\left(K(1)K(g)+K(g^3)K(g^4)\right)=2kK(1)(K(g)-K(g^3)),\]since $g$ is not a quadratic residue. Finally, we get \[K(1)^2+2K(g)^2=16p. \]Modulo $8$ on both sides we get $4|K(1)$ and $2|K(g)$, and remember that $\frac{-1}{2}K(1)\equiv r\pmod{p}$. Suppose by contradiction that $r=a^2$, then $-K(1)/2=a^2$ or $a^2-p$. In the first case, say $a=2b$ and \[a^4+2(K(g)/2)^2=4p,\]implies $K(g)/2$ also is even. But this implies that LHS is divided by $8$ which is impossible. In the second case, say $a=2b+1$, then \[8|(a^2-p)=4b^2+4b-8k\]still implies $K(g)/2$ is even and \[(K(1)/2)^2+2(K(g)/2)^2=4p\]is divided by $8$, contradict again. Hence $r$ is not square.