Exercise 3.1.6 (Minimum value of $|n^2 - 17x|$, where $x \in \mathbb{Z}$.)

Proof.

(a)

List of quadratic residues of each of the primes $7,13,17,29,37$: $$\begin{array}{llll}\hfill p=7:& 1,-3,2;& \hfill & \\ \hfill p=13:& \pm 1,\pm 3,\pm 4;& \hfill & \\ \hfill p=17:& \pm 1,\pm 2,\pm 4,\pm 8;& \hfill & \\ \hfill p=29:& \pm 1,\pm 4,\pm 5,\pm 6,\pm 7,\pm 9,\pm 13;& \hfill & \\ \hfill p=37:& \pm 1,\pm 3,\pm 4,\pm 7,\pm 9,\pm 10,\pm 11,\pm 12,\pm 16.& \hfill & \end{array}$$

At the exception of $7$, these primes $p$ are of the form $4k+1$, thus $-1$ is a quadratic residue, thus if $a$ is a quadratic residue modulo $p$, so is $-a$.

     sage: def least_remainder(a,b):
     ....:     r = a % b
     ....:     if 2 * r > b:
     ....:         r = r - b
     ....:     return r
     ....:
     sage: p = 37
     sage:l = [least_remainder(n^2, p) for n in range(1 + (p-1) // 2)];
                  l.sort(); l
     [-16, -12, -11, -10, -9, -7, -4, -3, -1,
          0, 1, 3, 4, 7, 9, 10, 11, 12, 16]

(b)

Let $n$ a fixed positive integer. The Euclidean division of $n^2$ by $17$ give $q,r$ such that $$n^2=17q+r,0\le r<17.$$

Define $q^{\prime },r^{\prime }$ by

$$\begin{array}{ccc}{q}^{\prime }=q+1,\hfill & r^{\prime }=r-17,\hfill & \text{if }r>8,\hfill \\ q^{\prime }=q,\hfill & r^{\prime }=r,\hfill & \text{if }r\le 8.\hfill \end{array}$$

Since $n^2=17(q+1)+(r-17)$, in both cases,

$$n^2=17q^{\prime }+r^{\prime },-8\le r^{\prime }\le 8.$$

(We call $r^{\prime }$ the least remainder in the division of $n^2$ by $17$.)

We prove that

$$|r^{\prime }|=\min <!--\; FUNCTION\; APPLICATION\; -->\{|n^2-17x|,x\in \mathbb{Z}\}.$$

Indeed, let

$$A_n=\{|n^2-17x|,x\in \mathbb{Z}\}=\{y\in \mathbb{Z}\mid \exists <!--\; FUNCTION\; APPLICATION\; -->x\in \mathbb{Z},y=|n^2-17x|\}.$$

Then $|r^{\prime }|=|n^2-17q^{\prime }|\in A_n$. If $y\in A_n$, where $y\ne |r^{\prime }|$, then $y=|n^2-17x|$ for some integer $x=q^{\prime }+h,h\ne 0$. Then

$$\begin{array}{llll}\hfill y=|n^2-17x|& =|n^2-17(q^{\prime }+h)|& \hfill & \\ \hfill & =|n^2-17q^{\prime }-17h|& \hfill & \\ \hfill & \ge 17|h|-|n^2-17q^{\prime }|& \hfill & \\ \hfill & \ge 17-8=9& \hfill & \\ \hfill & >|r^{\prime }|.& \hfill & \end{array}$$

Define $F(n)=\min <!--\; FUNCTION\; APPLICATION\; -->(A_n)$ to be the minimum value of $|n^2-17x|$, where $x$ runs over all integers. We have proved that $F(n)=|r^{\prime }|$, where $r^{\prime }$ is the least remainder of $n^2$ by $17$.

Since $n^2-17q^{\prime }=\pm |r^{\prime }|=\pm F(n)$, $\pm F(n)\equiv n^2(\mathit{mod}17)$, so $\pm F(n)$ is zero, or a quadratic residue modulo $17$. Since $-1$ is a quadratic residue modulo $17$, $F(n)$ is zero, or a quadratic residue modulo $17$, and $0\le F(n)=|r^{\prime }|\le 8$. By part (a),

$$F(n)\in \{0,1,2,4,8\}.$$

This shows that $F(n)$ is either $0$ or a power of $2$.