лемма

[rightways]

$ a $ и $n-$ взаимно простые натуральные числа. Докажите, что существует два натуральных числа $x,y$ для которых выполнено сравнение $a^2x^2\equiv y^2(mod n^2)$ и неравенство $n>x,y$.

[maxal]

Если ослабить неравенство $x,y<n$ до $x^2+y^2<3^{3/2} n^2$, то возможно такое решение:

Рассмотрим решетку, порождённую вектор-столбцами матрицы:

$$\begin{bmatrix}m\cdot a & m & m\cdot n^2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix},$$

где $m=3^{3/4}n$. По теореме Минковского кратчайший вектор в этой решетке имеет длину не превосходящую $\sqrt{3}\cdot (m\cdot n^2)^{1/3}=3^{3/4}n=m$. Нетрудно понять, что этот вектор имеет вид:

$$\begin{bmatrix}m\cdot a & m & m\cdot n^2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}\cdot \begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}0\\x\\y\end{bmatrix},$$

где $ax + y + zn^2 = 0$, а квадрат длины этого вектора удовлетворяет неравенству $x^2+y^2 < 3^{3/2} n^2$. Поэтому $a^2x^2\equiv y^2\pmod{n^2}$, а значит $x,y$ - искомые (с точностью до знака).

Вероятно, исходная задача решается уточнением теоремы Минковского в размерности 3.

[rightways]

А можете доказать без минковского если еще известно , что $a-1$ или $a+1$ делится на $n$.?

[Null]

Рассмотрим $ak=l_k n+d_k (\mod n^2)$ где $0<k<n$ и $0\le l_k,d_k<n$. На самом деле $d_k \ne 0$.
Если $l_k=0$ то $ak - d_k$ делиться на $n^2$.
Если $l_k=n-1$ то $ak+(n-d_k)$ делиться на $n^2$
Иначе $l_s=l_t$(по принципу Дирихле) и $a(s-t)-(d_s-d_t)$ делиться на $n^2$ Причем $0<|d_s-d_t|<n$ и $0<|s-t|<n$