Definición de residuos cuadráticos

Question

De acuerdo a Wikipedia, $q$ es un residuo cuadrático $\mod n$ si existe un entero $x$ tal que $x^2 \equiv q \mod n$. Algunas otras fuentes agregar el supuesto de que $q$ $n$ son coprime. Cual es la correcta?

Answer 1

Conceptualmente, la diferencia entre las dos definiciones no es importante.

Deje $(q,n)=d$$\frac qQ=\frac nN=d$, de modo que $(Q,N)=1$

$$\text{So, }x^2\equiv q\pmod n-->(1)\iff x^2=q+u\cdot n\text{ where } u \text{ is some integer }$$

$$\implies x^2= Qd+u\cdot Nd=d(Q+u\cdot N) $$

Ahora, si $d=a\cdot D^2$(por ejemplo) donde $D$ es un número entero y entero $a$ es la plaza libre.

$$\text{So, }\frac{x^2}{D^2}=a(Q+u\cdot N) \text{ which is an integer}$$

$\implies D^2\mid x^2\iff D\mid x\implies \frac xD$ es un número entero $=y$(decir)

$$\text{So, }\frac{y^2}a\equiv Q+u\cdot N \text{ which is an integer}$$

Como $a$ es de square-gratis, $a\mid y^2\iff a\mid y\implies \frac ya$ es un número entero $=z$(decir)

$$\text{So, }a\cdot z^2= Q+u\cdot N \equiv Q\pmod N,$$ $$z^2\equiv a^{-1}\cdot Q\pmod N-->(2)\text{ where} (Q,N)=1$$

Así, siempre podemos encontrar un entero $z$ satisfacción $(2)$ para cada entero $x$ satisfacción $(1)$ y vice-versa.