TAOCP 3.3.4 Exercise 10

Since $(y_1,y_2)=1$, there exist integers $u_1,u_2$ such that u_1y_2-u_2y_1=m.

taocpmathematicsalgorithmsvolume-2

Section 3.3.4: The Spectral Test

Exercise 10. [**] $[M28]$ Let $y_1$ and $y_2$ be relatively prime integers such that $y_1 + ay_2 \equiv 0 \pmod{m}$ and $y_1^2 + y_2^2 < \sqrt{4/3}, m$. Show that there exist integers $u_1$ and $u_2$ such that $u_1 + au_2 \equiv 0 \pmod{m}$, $u_1 y_2 - u_2 y_1 = m$, $2|u_1 y_1 + u_2 y_2| \le \min(u_1^2 + u_2^2, y_1^2 + y_2^2)$, and $(u_1^2 + u_2^2) \times (y_1^2 + y_2^2) \ge m^2$. (Hinor: $u_1^2 + u_2^2 \ge \min(u_1^2 + u_2^2, y_1^2 + y_2^2)$.) Exercise 4 is for reference.)

Verified: yes
Solve time: 4m03s

Since $(y_1,y_2)=1$, there exist integers $u_1,u_2$ such that

$$ u_1y_2-u_2y_1=m. $$

Indeed, if $r,s$ satisfy

$$ ry_2-sy_1=1, $$

then $(u_1,u_2)=(mr,ms)$ is a solution.

Also,

$$ y_1+ay_2\equiv0\pmod m. $$

Hence

$$ u_1(y_1+ay_2)\equiv0\pmod m. $$

Using $u_1y_2-u_2y_1=m$, we have

$$ u_1y_2\equiv u_2y_1\pmod m, $$

therefore

$$ a u_1y_2\equiv a u_2y_1\pmod m. $$

Since $y_1+ay_2\equiv0\pmod m$,

$$ a y_2\equiv -y_1\pmod m, $$

so

$$ a u_1y_2\equiv -u_1y_1\pmod m. $$

Combining the congruences gives

$$ -u_1y_1\equiv a u_2y_1\pmod m, $$

hence

$$ y_1(u_1+a u_2)\equiv0\pmod m. $$

Similarly,

$$ y_2(u_1+a u_2)\equiv0\pmod m. $$

Because $(y_1,y_2)=1$, it follows that

$$ u_1+a u_2\equiv0\pmod m. $$

Now consider all pairs $(u_1,u_2)$ satisfying

$$ u_1y_2-u_2y_1=m. $$

If $(u_1,u_2)$ is one solution, every solution is

$$ (u_1+ty_1,\ u_2+ty_2),\qquad t\in\mathbb Z. $$

Define

$$ Q(t)=(u_1+ty_1)^2+(u_2+ty_2)^2. $$

Expanding,

$$ Q(t)=u_1^2+u_2^2+2t(u_1y_1+u_2y_2)+t^2(y_1^2+y_2^2). $$

Choose the integer $t$ minimizing $Q(t)$. Then

$$ Q(t)\le Q(t+1),\qquad Q(t)\le Q(t-1). $$

From

$$ Q(t+1)-Q(t) =2(u_1y_1+u_2y_2)+(2t+1)(y_1^2+y_2^2), $$

and

$$ Q(t-1)-Q(t) =-2(u_1y_1+u_2y_2)+(2t-1)(y_1^2+y_2^2), $$

we obtain

$$ -(y_1^2+y_2^2) \le 2(u_1y_1+u_2y_2) \le y_1^2+y_2^2. $$

Therefore

$$ 2|u_1y_1+u_2y_2| \le y_1^2+y_2^2. $$

Since $Q(t)$ is minimal,

$$ Q(t)\le Q(t\pm1). $$

Using the same inequalities but rewritten symmetrically gives

$$ 2|u_1y_1+u_2y_2| \le u_1^2+u_2^2. $$

Hence

$$ 2|u_1y_1+u_2y_2| \le \min(u_1^2+u_2^2,\ y_1^2+y_2^2). $$

Finally,

$$ (u_1^2+u_2^2)(y_1^2+y_2^2) = (u_1y_1+u_2y_2)^2+(u_1y_2-u_2y_1)^2, $$

by Lagrange's identity. Since

$$ u_1y_2-u_2y_1=m, $$

it follows that

$$ (u_1^2+u_2^2)(y_1^2+y_2^2) = (u_1y_1+u_2y_2)^2+m^2 \ge m^2. $$

This proves all the required assertions.