# Wilson's theorem and congruence

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

• In the first part, $pq$ will be of the form $4k+1$, not $4k+3$. For example, $3 \cdot 11 = 33 = 4(8)+1$. – William Ballinger Jan 30 '14 at 15:39
• But if that's true then doesn't that mean that the equation has solutions? Are you able to help??? – 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.$
• @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.\$ – Bill Dubuque Jan 30 '14 at 18:55