Zeigen Sie, dass solche $x$ und $y$ existieren [Duplikat]

Dec 24 2020

Lassen $n$sei eine positive ganze Zahl, die kein Quadrat ist. Beweisen Sie das für jede ganze Zahl$a$ relativ gut zu $n$gibt es ganze Zahlen $x$ und $y$ befriedigend $$ax \equiv y \pmod{n}\text{ with } 0<x<\sqrt n \text{ and } 0<|y|<\sqrt n$$

Ich kann mit diesem Problem keine Fortschritte erzielen. Jede Hilfe wird geschätzt.

Antworten

2 Tan Dec 24 2020 at 20:11

Schau dir nur den Ausdruck an $ax-y$ zum $x,y$ $\in \{0,...,\lfloor\sqrt n\rfloor \}$. Beachten Sie, dass es gibt$(\lfloor\sqrt n\rfloor \ +1)^2 > n$ Möglichkeiten für $(x,y)$. Weil dort sind$n$ mögliche Werte für $ax-y \pmod n$Nach dem Pigeonhole-Prinzip gibt es verschiedene $(x_1,y_1), (x_2,y_2)$ im vorherigen Bereich mit $ax_1-y_1 \equiv ax_2-y_2 \pmod n$. So,$a(x_1-x_2) \equiv y_1-y_2 \pmod n$. Jetzt nimm$x=\lvert x_1-x_2 \rvert$, und, $y=y_1-y_2$ oder $y=-(y_1-y_2)$ abhängig vom Vorzeichen von $x$. Deutlich,$x,\lvert y \rvert \in \{0,...,\sqrt n\}$. Wir haben auch$x\neq \sqrt n$, und, $\lvert y \rvert \neq \sqrt n$, schon seit $n$ist kein Quadrat. Es bleibt nur zu zeigen, dass$x\neq 0$, und, $\lvert y \rvert \neq 0$, was leicht mit der Tatsache gemacht werden kann, dass $(x_1,y_1)$ und $(x_2,y_2)$ sind verschieden und $(a,n)=1$.