そのようなことを示す $x$ そして $y$ 存在する[重複]

Question

しましょう $n$正方形ではない正の整数である。すべての整数についてそれを証明する$a$ 互いに素 $n$、整数が存在します $x$ そして $y$ 満足 $$ax \equiv y \pmod{n}\text{ with } 0<x<\sqrt n \text{ and } 0<|y|<\sqrt n$$

私はこの問題を進展させることができません。どんな助けでもありがたいです。

Answer 1

式を見てください $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$。