Contar pares $(n,n+1)$ donde $n$ y $n+1$ son ambos residuos cuadráticos, etc.?

Question

He leído un problema interesante que me tiene perplejo.

Sea $(RR)$ denotan el número de pares $(n,n+1)$ en el conjunto $\{1,2,\dots,p-1\}$ tal que $n$ y $n+1$ son ambos residuos módulo $p$ . Sea $(NR)$ denotan los pares en los que $n$ es un no-residuo, y $n+1$ es un residuo módulo $p$ . Haga lo mismo para $(NN)$ y $(RN)$ .

La pregunta es, ¿cuáles son $(RR)+(RN),(NR)+(NN),(RR)+(NR),(RN)+(NN)$ ?

Sé que si $g$ es una raíz primitiva, entonces los residuos son las potencias pares de $g$ y los no-residuos son las potencias Impares de $g$ . Así que los pares en $(RR)$ tienen forma $(g^{2k},g^{2j})$ y me gustaría contar los pares que se pueden expresar como $n=g^{2k},n+1=g^{2j}$ . Esto implica $g^{2j}-g^{2k}=1=g^{p-1}$ . Podría establecer ecuaciones similares para los otros tres tipos de pares, pero no veo nada bonito a lo que agarrarme y con lo que trabajar. Tal vez calcular $(RR)+(RN)$ es más fácil que calcular $(RR)$ y $(RN)$ ¿por separado por alguna razón?

¿Cómo se podría abordar su cálculo? Muchas gracias.

Fuente: Irlanda/Rosen #5.29

Answer 1

Sea $p$ ser impar. Nos fijamos en $(RR)+(RN)$ . Este es casi el número de QR. La única forma de que una QR no vaya seguida de una QR o una NR es que la QR esté en $p-1$ . Este es el caso si $p\equiv 1\pmod{4}$ .

Así que cuando $p\equiv 1\pmod{4}$ tenemos $(RR)+(RN)=\frac{p-1}{2}-1$ . En $p\equiv -1\pmod{4}$ tenemos $(RR)+(RN)=\frac{p-1}{2}$ . No he hecho las otras preguntas. Son muy parecidas. Para las dos últimas tenemos que viajar hacia atrás, y observar que $1$ es siempre un QR.

Answer 2

Para calcular por separado, véase Apostol Capítulo 9 Ex 5, p201.

Con $\alpha$ , $\beta$ en $\pm1$ deje $N(\alpha,\beta)$ denotan el número de enteros $x$ en $1,2,\dots,p-2$ tal que $(x|p)=\alpha$ y $(x+1|p)=\beta$ donde $p$ es un primo impar. Así que $N(1,-1)=(RN)$ arriba. Entonces

$4N(\alpha,\beta)=\displaystyle\sum_{x=1}^{p-2}(1+\alpha(x|p))(1+\beta(x+1|p))$

desde $1+\alpha(x|p)=2$ si $(x|p)=\alpha$ y es $0$ por otra parte. Del mismo modo para $\beta$ para que $(1+\alpha(x|p))(1+\beta(x+1|p))=4$ si $(x|p)=\alpha$ y $(x+1|p)=\beta$ y es $0$ de lo contrario.

Expandiendo la suma obtenemos

$4N(\alpha,\beta)=p-2-\beta-\alpha\beta-\alpha(-1|p)$

utilizando

$\displaystyle\sum_{x=1}^{p-2}(x|p)=-(-1|p)$ ; $\displaystyle\sum_{x=1}^{p-2}(x+1|p)=-1$ y $\displaystyle\sum_{x=1}^{p-2}(x(x+1)|p)=-1$ .