Let $p$ be an odd prime number. For every integer $r \in \mathbb{Z}$, we denote by $\varphi(r)$ the remainder of the Euclidean division of $r^2$ by $p$. We thus have $0 \leqslant \varphi(r) \leqslant p - 1$ and $r^2 - \varphi(r) \in p\mathbb{Z}$. a) Show that the restriction of $\varphi$ to $\left\{0, \ldots, \frac{p-1}{2}\right\}$ is injective. b) We consider the sets $X = \left\{p - \varphi(r) \left\lvert\, 0 \leqslant r \leqslant \frac{p-1}{2}\right.\right\}$ and $Y = \left\{\varphi(s) + 1 \left\lvert\, 0 \leqslant s \leqslant \frac{p-1}{2}\right.\right\}$. Show that $X$ and $Y$ are contained in $\{1, \ldots, p\}$ and that their intersection is non-empty. Deduce that there exist $u, v \in \left\{0, \ldots, \frac{p-1}{2}\right\}$ and $m \in \{1, \ldots, p-1\}$ such that $u^2 + v^2 + 1 = mp$.
Let $p$ be an odd prime number. For every integer $r \in \mathbb{Z}$, we denote by $\varphi(r)$ the remainder of the Euclidean division of $r^2$ by $p$. We thus have $0 \leqslant \varphi(r) \leqslant p - 1$ and $r^2 - \varphi(r) \in p\mathbb{Z}$.\\
a) Show that the restriction of $\varphi$ to $\left\{0, \ldots, \frac{p-1}{2}\right\}$ is injective.\\
b) We consider the sets $X = \left\{p - \varphi(r) \left\lvert\, 0 \leqslant r \leqslant \frac{p-1}{2}\right.\right\}$ and $Y = \left\{\varphi(s) + 1 \left\lvert\, 0 \leqslant s \leqslant \frac{p-1}{2}\right.\right\}$.
Show that $X$ and $Y$ are contained in $\{1, \ldots, p\}$ and that their intersection is non-empty. Deduce that there exist $u, v \in \left\{0, \ldots, \frac{p-1}{2}\right\}$ and $m \in \{1, \ldots, p-1\}$ such that $u^2 + v^2 + 1 = mp$.