For which positive integers n do there exist integers x and y such with (x, n) = 1, (y, n) = 1, such that $\displaystyle x^2+y^2 \equiv 0\ (mod\ n)$?

Printable View

- Jul 21st 2011, 04:02 PMalexmahoneAnother quadratic reciprocity problem
For which positive integers n do there exist integers x and y such with (x, n) = 1, (y, n) = 1, such that $\displaystyle x^2+y^2 \equiv 0\ (mod\ n)$?

- Jul 21st 2011, 05:04 PMalexmahoneRe: Another quadratic reciprocity problem
It is easy to see that n = 2 satifies the given congruence. If n is odd, every prime p dividing n should satisfy $\displaystyle \left(\frac{-y^2}{p}\right)=1 \implies \left(\frac{-1}{p}\right)=1 \implies p \equiv 1\ (mod\ 4)$.

The answer given in the book is: $\displaystyle n=2^{\alpha}\prod p^{\beta}$ where $\displaystyle \alpha$ = 0 or 1, the primes p in the product are all $\displaystyle \equiv 1\ (mod\ 4)$, and $\displaystyle \beta=\beta(p)=0,1,2,...$.

How do they get the $\displaystyle 2^\alpha$ in the product?