2
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah, that's nice. $\endgroup$
    – usr0192
    Aug 10, 2016 at 5:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .