Número de soluciones al $x_1x_2+x_3x_4 = 1$ (mod $n$)

Question

Muestran que el número de soluciones es $N$ $x_1x_2+x_3x_4 = 1 \pmod n$

$$ N = n ^ 2\phi \prod_ (n) {p | n} \left (1 + \frac {1} {p} \right). $$

Lo único sabe cómo iniciar el problema debe considerar:

N $ = \frac{1}{n} \sum_{k=0}^{n-1}S_k^2 e(-\frac{k}{n}), $ donde $$ S_k=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}e(\frac{kxy}{n}). $$

Pero no tengo idea que hacer por una suma así a la conclusión.

Answer 1

Para probar esto, mostrar que la identidad tiene modulo $p$ por cada $p$, y, a continuación, utilizar el teorema del resto Chino.

En particular, modulo $p$, podemos dejar que la $x_1,x_2$ tomar cualquier valor. Una fracción $\frac{p^2-p+1}{p^2}$ del tiempo de la cantidad de $1-x_1 x_2$ va a ser distinto de cero, y $\frac{p-1}{p^2}$ del tiempo que será igual a $0$. En el primer caso, no se $p-1$ opciones para $x_3$, e $1$ opción para $x_4$. En el segundo caso, habrá un total de $2p-1$ opciones para $x_3$ $x_4$ ya que sólo necesitamos tener $1$ de ellos igual a $0$. Por lo tanto el número de soluciones modulo $p$ $$p^2\left(\frac{p^2-p+1}{p^2}(p-1)+\frac{p-1}{p^2}(2p-1)\right)=p(p^2-1)=p^2\phi(p)\left(1+\frac{1}{p}\right).$$