ऐसे दिखाओ $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$।