Show that the number of solutions $N$ to $x_1x_2+x_3x_4 = 1 \pmod n$ is
$$ N=n^2\phi(n)\prod_{p|n} \left( 1+\frac{1}{p} \right). $$
Only thing I know how to start the problem is to consider:
$$ N = \frac{1}{n} \sum_{k=0}^{n-1}S_k^2 e(-\frac{k}{n}), $$ where $$ S_k=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}e(\frac{kxy}{n}). $$
But I have no idea what to do for a sum like this to conclude.
To prove this, show that the identity holds modulo $p$ for every $p$, and then use the Chinese remainder theorem.
In particular, modulo $p$, we can let $x_1,x_2$ take any values. A fraction $\frac{p^2-p+1}{p^2}$ of the time the quantity $1-x_1 x_2$ will be non-zero, and $\frac{p-1}{p^2}$ of the time it will equal $0$. In the first case, there are $p-1$ choices for $x_3$, and $1$ choice for $x_4$. In the second case there will be a total of $2p-1$ choices for $x_3$ and $x_4$ since we need only have $1$ of them equal to $0$. Thus the number of solutions modulo $p$ is $$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).$$