Oops, queste sono tutte le scemenze che scrivo alle $3$ di notte
Cerco di spiegare/ aggiustare/ riempire i buchi che ho lasciato. Innanzitutto $p=2n+1$.
Consideriamo i due insiemi:
$$R:= \{a^2 \mid a=0,1, \dots , \frac {p-1}{2} \} \ \ , \ \ S:= \{ -b^2-1 \mid b=0,1, \dots , \frac {p-1}{2} \}$$
Supponiamo per assurdo che vi siano due elementi in $R$ che sono congrui modulo $p$, allora si avrebbe:
$$a^2 \equiv c^2 \pmod p \iff (a+c)(a-c) \equiv 0 \pmod p \iff p \mid (a+c) \ \ \text{o} \ \ p \mid (a-c)$$
Ma dato che $a-c,a+c \leq 2n <p$ e $a,c \geq 0$ si ottiene che $a=c$.
In modo del tutto identico si dimostra che non vi sono due elementi congrui modulo $p$ in $S$.
Osserviamo inoltre che gli elementi in $R$ sono tutti $\geq 0$ , mentre gli elementi in $S$ sono tutti $<0$ , quindi $R \cap S= \emptyset$.
Ma se consideriamo ora $T=R \cup S$ otteniamo che $T$ ha $2n+2=p+1$ elementi. Quindi vi saranno due elementi in $T$ che sono congrui modulo $p$, ma per quanto detto all'inizio, un elemento proviene da $R$ mentre l'altro proviene da $S$. Quest'ultima affermazione è equivalente a dire che :
$$a^2+b^2+1=kp$$ ha sempre soluzione.
Ho cambiato la dimostrazione in parte poiché era questa quella che avevo in mente. Hai ragione, avevo completamente omesso il fatto che il mio polinomio $P(x)$ ha al più due radici! In particolare, $m$ era una generica classe di resto a cui $a^2$ era congruo modulo $p$. Il mio polinomio in questo caso ne ha esattamente $2$ modulo $p$ , ovvero sia $a$ che $-a$ , ma dato che $-a \equiv p-a \pmod p$ e per il discorso iniziale $a^2$ è congruo ad esattamente $1+ \dfrac {p-1}{2}$ classi di resto distinte, si ottiene che i residui quadratici sono esattamente $1+ \dfrac {p-1}{2}$.