# p quadratic residue mod q implies it is one mod 4q

Let $p, q$ be distinct odd primes, and with $p \equiv 1 \mod \ 4$. If $p \equiv x^2 \mod\ q$ for some integer $x$ (i.e. $p$ is a quadratic residue mod q), then show $p \equiv b^2 \mod\ 4q$ for some odd integer $b$.

Cox's book "Primes of the form x^2 + ny^2" on p.14 says (something slightly more general than the above) is straightforward, but I'm not seeing how.

• How can you deduce $x$ is even? $x$ is only defined up to a multiple of $q$ so its oddness/evenness should be irrelevant. Aug 10, 2016 at 4:55
• @ErickWong You are right. My mistake. I removed that part now. Aug 10, 2016 at 4:59

We have $$p\equiv1^2\pmod4$$ and $$p\equiv b^2\pmod q.$$ Because $\gcd(4,q)=1$ the Chinese Remainder Theorem tells there exists an integer $x$ such that $x\equiv1\pmod4$ and $x\equiv b\pmod q$. Then $x^2-p$ is divisible by both $4$ and $q$.
We are free to assume that $x$ is odd, for if $x$ is even we can just replace $x$ by $x+q$ (or $q-x$) without affecting the congruence $p\equiv x^2 \pmod q$. Now take $b=x$: clearly $4 \mid p - b^2$ (since $p$ and $b^2$ are both $1$ mod $4$), and $q \mid p-b^2$ (by assumption), so $4q \mid p-b^2$ since $q$ and $4$ are relatively prime.