[11 points] In the XY plane, draw horizontal and vertical lines through each integer on both axes so as to get a grid of small $1 \times 1$ squares whose vertices have integer coordinates.
(i) Consider the line segment $D$ joining $(0,0)$ with $(m,n)$. Find the number of small $1 \times 1$ squares that $D$ cuts through, i.e., squares whose interiors $D$ intersects. (Interiors consist of points for which both coordinates are non-integers.) For example, the line segment joining $(0,0)$ and $(2,3)$ cuts through 4 small squares, as you can check by drawing.
(ii) Now $L$ is allowed to be an arbitrary line in the plane. Find the maximum number of small $1 \times 1$ squares in an $n \times n$ grid that $L$ can cut through, i.e., we want $L$ to intersect the interiors of maximum possible number of small squares inside the square with vertices $(0,0)$, $(n,0)$, $(0,n)$ and $(n,n)$.

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$.