Contando las soluciones de $x^2 \equiv y^2-d \pmod p$

Question

Así que me estoy leyendo "Un Clásico de Introducción a la Moderna Teoría de números", y necesito ayuda para una pregunta:

Mostrar que $$x^2 \equiv y^2-d \pmod p$$ has $p-1$ solutions for $\gcd(p,d)=1$ and $2p-1$ for $\gcd(p,d)>1$, where $p$ es un número primo mayor que 3.

Estoy un poco confundido, si la respuesta tanto ser $2p-1$?

Answer 1

Estamos buscando la congruencia $(x-y)(x+y)\equiv d\pmod{p}$. Si $d$ es divisible por $p$, las soluciones se $(a,a)$ $(a,-a)$ donde $a$ viajes de$0$$p-1$. Desde $p$ es impar, estos son todos distintos modulo $p$, excepto cuando se $a=0$. Así que hay $2(p-1)+1=2p-1$ soluciones.

Supongamos ahora que $d$ no es divisible por $p$. Deje $x-y = a$ donde $a$ viajes de $1$ $p-1$(claramente $y-x$ no puede ser congruente a $0$). Para cualquier $a$, no hay una única $b$ tal que $ab\equiv -d\pmod{p}$. A continuación, $x^2-y^2\equiv d\pmod{p}$ si y sólo si $x+y\equiv b\pmod{p}$.

Desde $p$ es impar, $2$ es invertible modulo $p$, y por lo tanto el sistema $x-y\equiv a\pmod p$, $x+y \equiv b\pmod{p}$ tiene una única solución a $(x,y)$ modulo $p$. De ello se desprende que hay muchas soluciones de la original de congruencia, ya que hay opciones para $a$, es decir,$p-1$. El caso de $p=3$ no es especial, podemos tomar $p \ge 3$.