Factoring product of two primes from solutions of congruence The algorithm purposed to play a fair game of heads or tails over the phone given here claims that knowing the four solutions to $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is a product of two unknown primes $p,q$ and $\gcd(a, n) = 1$. However, I am not seeing why this would be true. Can someone please explain?

Let $a_p$ be a square root of $a$ modulo $p$, and let $a_q$ be a square root of $a$ modulo $q$. The four square roots are given by numbers $x,y,z,w$ such that:

1. $x \equiv a_p \pmod{p}$ and $x \equiv a_q \pmod{q}$.
2. $y \equiv a_p \pmod{p}$ and $y \equiv -a_q \pmod{q}$.
3. $z \equiv -a_p \pmod{p}$ and $z \equiv a_q \pmod{q}$.
4. $w \equiv -a_p \pmod{p}$ and $w \equiv -a_q \pmod{q}$.



If you look at $x-y$, for example, then you find that $x-y \equiv 0 \pmod{p}$ and $x-y \equiv 2a_q \pmod{q}$. This means that $x-y$ is divisible by $p$ but not by $q$, and so $\mathrm{gcd}(x-y,n) = p$.