Покажи, что такое $x$ и $y$ существует [дубликат]

Dec 24 2020

Позволять $n$быть положительным целым числом, не являющимся квадратом. Докажите, что для каждого целого числа$a$ относительно простой $n$, существуют целые числа $x$ и $y$ удовлетворение $$ax \equiv y \pmod{n}\text{ with } 0<x<\sqrt n \text{ and } 0<|y|<\sqrt n$$

Я не могу решить эту проблему. Любая помощь будет оценена по достоинству.

Ответы

2 Tan Dec 24 2020 at 20:11

Вы только посмотрите на выражение $ax-y$ для $x,y$ $\in \{0,...,\lfloor\sqrt n\rfloor \}$. Обратите внимание, что есть$(\lfloor\sqrt n\rfloor \ +1)^2 > n$ возможности для $(x,y)$. Поскольку есть$n$ возможные значения для $ax-y \pmod n$, по принципу ячеек, существуют различные $(x_1,y_1), (x_2,y_2)$ в предыдущем диапазоне с $ax_1-y_1 \equiv ax_2-y_2 \pmod n$. Так,$a(x_1-x_2) \equiv y_1-y_2 \pmod n$. Теперь возьми$x=\lvert x_1-x_2 \rvert$, и, $y=y_1-y_2$ или $y=-(y_1-y_2)$ в зависимости от знака $x$. Ясно,$x,\lvert y \rvert \in \{0,...,\sqrt n\}$. У нас также есть$x\neq \sqrt n$, и, $\lvert y \rvert \neq \sqrt n$, поскольку $n$это не квадрат. Осталось только показать, что$x\neq 0$, и, $\lvert y \rvert \neq 0$, что легко сделать, используя тот факт, что $(x_1,y_1)$ и $(x_2,y_2)$ различны и $(a,n)=1$.