Thue's lemma on small nonzero representatives

The set $H:=\{k\in \mathbb{N}:k\le p\text{ and }{k}^2<p\}$ is finite and contains $0$, so [L1] gives its largest element $h$.

One has $(h+1{)}^2>p$: a strict inequality in the other direction would put $h+1$ in $H$, while equality would factor the prime $p$ as $(h+1)(h+1)$ with $1<h+1<p$. Also $h^2<p=(\sqrt{p}{)}^2$, so $h<\sqrt{p}$ by nonnegativity and [L2].

Put $I:=\{0,1,\dots ,h\}$. Then [L3] gives $\mathrm{\mid }I\times I\mathrm{\mid }=(h+1{)}^2>p=\mathrm{\mid }\mathbb{Z}\mathrm{/}p\mathrm{\mid }$ by step 2.1 and [L4].

Apply [L5] to $(i,j)\mapsto [ia-j{]}_p$. Distinct pairs $(i,j),(i^{\mathrm{\prime }},j^{\mathrm{\prime }})\in I\times I$ have the same image. With $r=i-i^{\mathrm{\prime }}$ and $s=j-j^{\mathrm{\prime }}$, this says $ra\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

The coordinate bounds give $\mathrm{\mid }r\mathrm{\mid },\mathrm{\mid }s\mathrm{\mid }\le h<\sqrt{p}$.

If $r=0$, then [F1] gives $p\mid s$; the bound $\mathrm{\mid }s\mathrm{\mid }<\sqrt{p}<p$ forces $s=0$, contrary to distinctness. If $s=0$, then $p\mid ra$; [L6] and $p\nmid a$ give $p\mid r$, and the same bound forces $r=0$, again a contradiction.

Thus the integers $r,s$ from step 4.1 are both nonzero, satisfy $ra\equiv s(\mathrm{m}\mathrm{o}\mathrm{d}p)$, and obey the required strict bounds.