Mostre que tal $x$ e $y$ existe [duplicado]

Dec 24 2020

Deixei $n$ser um número inteiro positivo que não é um quadrado. Prove que para cada inteiro$a$ relativamente primo para $n$, existem inteiros $x$ e $y$ satisfatório $$ax \equiv y \pmod{n}\text{ with } 0<x<\sqrt n \text{ and } 0<|y|<\sqrt n$$

Não consigo fazer nenhum progresso com este problema. Qualquer ajuda será apreciada.

Respostas

2 Tan Dec 24 2020 at 20:11

Basta olhar para a expressão $ax-y$ para $x,y$ $\in \{0,...,\lfloor\sqrt n\rfloor \}$. Observe que existem$(\lfloor\sqrt n\rfloor \ +1)^2 > n$ possibilidades para $(x,y)$. Uma vez que existem$n$ valores possíveis para $ax-y \pmod n$, pelo princípio do escaninho, existe uma $(x_1,y_1), (x_2,y_2)$ na faixa anterior com $ax_1-y_1 \equiv ax_2-y_2 \pmod n$. Assim,$a(x_1-x_2) \equiv y_1-y_2 \pmod n$. Agora pegue$x=\lvert x_1-x_2 \rvert$, e, $y=y_1-y_2$ ou $y=-(y_1-y_2)$ dependendo do sinal de $x$. Claramente,$x,\lvert y \rvert \in \{0,...,\sqrt n\}$. Nos tambem temos$x\neq \sqrt n$, e, $\lvert y \rvert \neq \sqrt n$, Desde a $n$não é um quadrado. Tudo o que resta é mostrar que$x\neq 0$, e, $\lvert y \rvert \neq 0$, o que pode ser feito facilmente usando o fato de que $(x_1,y_1)$ e $(x_2,y_2)$ são distintos e $(a,n)=1$.