Prove that every odd prime divides a number of the form $l^2+m^2+1$ $(l,m\in \mathbb {Z})$ I understand this proof http://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Ng.pdf (Lemma 2.2) until the point "and hence of $-1 - m^2\mod p$ ". Why is this true, and how does the final line then follow?
 A: It's a classical proof that uses the Pigeonhole Principle. You can prove a more general result with the same method: 
If $p$ is an odd prime (it's clear when $p=2$), then for all $a,b,c\in\mathbb Z$ such that $p\nmid a,b$ exist $x,y\in\mathbb Z$ such that $p\mid ax^2+by^2+c$.
Proof: First I'll prove there are $(p+1)/2$ squares mod $p$. Notice 
$$r^2\equiv s^2\pmod{p}\iff (r+s)(r-s)\equiv 0\pmod{p}\iff r\equiv \pm s\pmod{p},$$
so $0, 1^2, 2^2,\ldots, ((p-1)/2)^2$ are all the squares mod $p$, so there are $(p+1)/2$ squares mod $p$.
Therefore, in the congruence $ax^2\equiv -by^2-c\pmod{p}$, the LHS can gain $(p+1)/2$ different values mod $p$ and the RHS can also gain $(p+1)/2$ different values.
Also $(p+1)/2+(p+1)/2=p+1$, so by the Pigeonhole Principle exists at least one solution $x,y\in\mathbb Z$. 
A: The map $x\mapsto -1-x$ is a bijection of the residues modulo $p$. Hence if $m^2$ runs through $n+1$ distinct residues, then $-1-m^2$ also runs through $n+1$ distinct residues.
After that, the two sets of residues (i.e., the $n+1$ residues of form $l^2\pmod p$ and the $n+1$ residues of form $-1-m^2\pmod p$) cannot be disjoint because there are only $p<(n+1)+(n+1)$ residues in total. Any element that is both of the form $l^2\pmod p$ and of the form $-1-m^2\pmod p$ then tells us that $l^2+1+m^2$ is a multiple of $p$.
A: All it's saying is that if $m_1^2 \not\equiv m_2^2 \bmod p$, then $-1-m_1^2 \not\equiv -1-m_2^2 \bmod p$. So the number of different values of $m^2 \bmod p$ is the same as the number of different values of $-1-m^2 \bmod p$.
