Tunjukkan itu $x$ dan $y$ ada [duplikat]

Question

Membiarkan $n$menjadi bilangan bulat positif yang bukan persegi. Buktikan itu untuk setiap bilangan bulat$a$ relatif prima $n$, ada bilangan bulat $x$ dan $y$ memuaskan $$ax \equiv y \pmod{n}\text{ with } 0<x<\sqrt n \text{ and } 0<|y|<\sqrt n$$

Saya tidak dapat membuat kemajuan apa pun dengan masalah ini. Bantuan apa pun akan dihargai.

Answer 1

Lihat saja ekspresinya $ax-y$ untuk $x,y$ $\in \{0,...,\lfloor\sqrt n\rfloor \}$. Perhatikan bahwa ada$(\lfloor\sqrt n\rfloor \ +1)^2 > n$ kemungkinan untuk $(x,y)$. Sejak ada$n$ nilai yang mungkin untuk $ax-y \pmod n$, dengan prinsip pigeonhole, ada perbedaan $(x_1,y_1), (x_2,y_2)$ dalam rentang sebelumnya dengan $ax_1-y_1 \equiv ax_2-y_2 \pmod n$. Begitu,$a(x_1-x_2) \equiv y_1-y_2 \pmod n$. Sekarang ambil$x=\lvert x_1-x_2 \rvert$, dan, $y=y_1-y_2$ atau $y=-(y_1-y_2)$ tergantung pada tandanya $x$. Jelas,$x,\lvert y \rvert \in \{0,...,\sqrt n\}$. Kami juga punya$x\neq \sqrt n$, dan, $\lvert y \rvert \neq \sqrt n$, sejak $n$bukan persegi. Yang tersisa hanyalah menunjukkan itu$x\neq 0$, dan, $\lvert y \rvert \neq 0$, yang dapat dilakukan dengan mudah menggunakan fakta itu $(x_1,y_1)$ dan $(x_2,y_2)$ berbeda dan $(a,n)=1$.