1. Establish that $x^2 \equiv −1 \pmod {pq}$ has no solutions if $p \equiv 3 \pmod 4$ or $q \equiv 3 \pmod 4$
  2. Show that if $p$ is an odd prime such that $p \equiv 1 \pmod 4$, then $x^2 \equiv −1 \pmod p$ has exactly two distinct solutions.
  3. Explain why in general $x^2 \equiv −1 \pmod {pq}$ has either zero or four solutions.

This is what I have done so far.

1) If $p \equiv 3 \pmod 4$ then $p$ is of the form $4k+3$ so $pq= 4kq+3q$, which is also of the form $4k+3$ (not sure about this part?). Suppose that the congruence $x^2 +1 \equiv 0 \pmod {4k+3}$ has a solution, that is there is an integer $a$ such that $a^2 \equiv -1 \pmod {4k +3}$. Applying Fermat's little theorem gives $4^4k+2 \equiv 1 \pmod {4k + 3} = (a^2)^2k+1 \equiv (-1)^2k+1 \equiv -1 \pmod {4k+3}$ giving the contradiction $1 \equiv -1 \pmod {4k+3}$. We can use similar reasoning for $q$. How then can I extend this to mod $pq$ or have I shown this already?

2) $p \equiv 1 \pmod 4$ so is of the form $4k+1$ and $x^2+1 \equiv 0 \pmod {4k+1}$ is satisfied when $x= (2k)!$. So the congruence has a solution... Now I'm stuck...

3) I don't even know where to start with this...

  • $\begingroup$ In the first part, $pq$ will be of the form $4k+1$, not $4k+3$. For example, $3 \cdot 11 = 33 = 4(8)+1$. $\endgroup$ – William Ballinger Jan 30 '14 at 15:39
  • $\begingroup$ But if that's true then doesn't that mean that the equation has solutions? Are you able to help??? $\endgroup$ – hannah668 Jan 30 '14 at 16:06

For $(1),\,$ note $\ pq\mid x^2+1\,\Rightarrow\, p,q\mid x^2+1,\,$ i.e. if a root exists mod $pq,\,$ it remains a root mod $p,q$.

For $(2),\,$ you know one root $\,a\,$ of $\,f(x) = x^2+1\,$ thus $\,f(x) = (x-a)(x+a).\,$ It has no other root $\,b\not\equiv \pm a\,$ since $\,f(b)\equiv0\,\Rightarrow\,p\mid f(b)=(b\!-\!a)(b\!+\!a)\overset{p\ \rm prime}\Rightarrow\!p\mid b\!-\!a\ $ or $\ p\mid b\!+\!a\,\Rightarrow b\equiv\pm a.$

For $(3),\,$ use the prior results and CRT. We know there are (two) solutions mod $p,q$ iff both $p,q\equiv 1\pmod{4}$. By CRT these correspond to $4$ solutions mod $\,pq,\,$ by $\,p\ne q\,\Rightarrow\,(p,q)=1.$

  • $\begingroup$ Ok, thanks so much :) but I'm still a bit confused and have some questions... 1) the first part seems to be the wrong way round because if p divides x^2+1 and q divides x^2+1 does this necessarily imply that pq divides x^2+1? 2) you say that we "know one root" a of x^2+1. How do we know this and how does x^2+1=(x-a)(x+a)? 3) how does p being prime eliminate the b from b+/-a? Thanks, Hannah $\endgroup$ – hannah668 Jan 30 '14 at 17:44
  • 1
    $\begingroup$ @hannah668 For $(1),\,$ if it had a solution mod $pq$ then it'd have one mod $p$ or $\,q\equiv 3\pmod4\,$ contra what you proved. For $(2)$ you know that $a = (2k)!$ is a root. So too is $-a$ since $(-a)^2 = a^2 \equiv -1$. For the final question, because $p$ is prime it follows that if $p$ divides a product then it divides some factor of the product. This is used in the above proof that if $b$ is any root of $x^2 + 1 = (x-a)(x+a)$ then $\,b\equiv a\,$ or $\,b\equiv -a,\,$ so $\pm a$ are the only roots mod $\,p.\ $ $\endgroup$ – Bill Dubuque Jan 30 '14 at 18:55
  • $\begingroup$ You're a star :) :) :) thanks so much :) :) :) $\endgroup$ – hannah668 Jan 31 '14 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.