Squares which are not 1 + a square in finite fields of odd characteristic? Given a finite field $F$ of odd characteristic, does there always exist an element $x$ of $F$ such that $1 + x^2$ is not a square in $F$? If so, can one even find a natural description of such an element, e.g. as a function of $\lvert F \rvert$ and a generator of $F^\times$?
 A: It is easy to show that such element always exists. 

Let $F$ be a finite field of odd characteristic, we copy the definition of Legendre symbol:
$$\bigg( \frac{a}{F}\bigg) = \begin{cases}1 \quad \text{ if } a\neq 0 \text{ is a square in } F \\-1 \quad \text{ if } a\neq0 \text{ not a square in } F \\0 \quad \text{ if } a=0 \end{cases}$$
Then you can show the following (the analogs for Legendre symbol is well-known):

$$\bigg( \frac{ab}{F}\bigg) = \bigg( \frac{a}{F}\bigg) \bigg(\frac{b}{F}\bigg)$$

Also, (again, the analogs for Legendre symbol is well-known)

$$\sum_{x\in F} \bigg(\frac{x}{F} \bigg) = 0$$
  $$\tag{1}\begin{equation}\sum_{x\in F} \bigg(\frac{x^2+ax+b}{F} \bigg) = -1 \quad \quad \text{if }a^2-4b\neq 0 \end{equation}$$

In particular, we have
$$\sum_{x\in F} \bigg(\frac{x^2+1}{F} \bigg) = -1$$
so some terms must be $-1$, this implies there is always an $x\in F$ such that $1+x^2$ is not a square in $F$.

I will outline the proof of $(1)$: completing the square, we only need to prove when $a\neq 0$, $$S_a = \sum_{x\in F} \bigg(\frac{x^2-a}{F} \bigg) = -1$$
Note that when $a,b$ are both residues or both non-residues, $S_a = S_b$. Let $u$ denote a non-residue. 
$$\sum_{a\in F} S_a = \sum_{x\in F}\sum_{a\in F} \bigg(\frac{x^2-a}{F} \bigg) = 0$$ because the inner sum is identically zero.
Hence $$\tag{2}S_0 + \frac{|F|-1}{2} S_1 + \frac{|F|-1}{2} S_u = 0 \implies S_1 + S_u = -2 $$
where we used the fact that $S_0 = |F|-1$.
Moreover, $$\sum_{a\in F} S_{a^2} = \sum_{a,x\in F} \bigg(\frac{x-a}{F} \bigg)\bigg(\frac{x+a}{F} \bigg) = \sum_{x\in F} \sum_{a\in F} \bigg(\frac{x+2a}{F} \bigg)\bigg(\frac{x}{F} \bigg) = 0$$
this implies $$S_0 + (|F|-1)S_1 = 0 \implies S_1 = -1$$
Combining with $(2)$ shows $S_a = -1$ whenever $a\neq 0$.
A: Short answer I found to the existence part of my question.
Let $\lvert F \rvert = p^n$ for some odd prime $p$ and a natural number $n$. The number of squares in $F$ is given by $\frac{p^n + 1}{2}$, a number not divisible by $p$. If we would have that $1 + x^2$ is always a square, then any orbit of the action of $+1$ would either contain no squares or consist entirely of squares. That is, for any square $x^2$, also $x^2 + 1, x^2 + 2, \ldots, x^2 + (p - 1)$ would be squares.
In particular, the number of squares would be a multiple of $p$, as every orbit of this action contains $p$ elements. Contradiction.
A: For $F=\mathbb{F}_p$ we can use the usual Legendre symbol to find such an $x$. For example, we can choose $x=-1$, and then
$1+x^2=2$ is not a square in $F$ if and only if 
$$
\left( \frac{2}{p}\right)=-1,
$$
i.e., if and only if $p\equiv 3,5\bmod 8$. For the cases $p\equiv 1,7\bmod 8$ we may chose a different $x$. In general, for $F=\mathbb{F}_{p^n}$ this is more complicated, but we may use the Legendre symbol $(a/F)$ as in the answer above.
