6.3 Square roots mod \(p\) and mod \(pq\)
Let \(p\) be an odd prime. Then the congruence \(\,x^2+1\equiv 0 \text{ mod }(p)\) has a solution if and only if \(p\equiv 1 \text{ mod }(4)\).
Proof. Suppose that \(p\) is an odd prime, and let \(k=(p-1)/2\). In the product \[(p-1)!=1\times 2\times\cdots\times k\times(k+1)\times\cdots\times(p-2)\times(p-1)\,,\] we have \(p-1\equiv -1,\, p-2\equiv -2,\, \ldots,\, k+1=p-k\equiv -k\text{ mod }(p)\), so by replacing each of the \(k\) factors \(p-i\) with \(-i\) for \(i=1,\ldots,k\) we see that \[(p-1)!\equiv (-1)^k.(k!)^2\;\;\text{ mod }(p)\,.\]
Now Wilson’s Theorem gives \((p-1)!\equiv -1\), so \((-1)^k(k!)^2\equiv -1\) and hence \((k!)^2\equiv (-1)^{k+1}\). If \(p\equiv 1\text{ mod }(4)\) then \(k\) is even, so \((k!)^2\equiv -1\) and hence \(x=k!\) is a solution of \(x^2+1\equiv 0\text{ mod }(p)\).
On the other hand, suppose that \(p\equiv 3\text{ mod }(4)\), so that \(k=(p-1)/2\) is odd. If \(x\) is any solution of \(x^2+1\equiv 0\text{ mod }(p)\), then \(x\) is coprime to \(p\), so Fermat’s Little Theorem gives \(x^{p-1}\equiv 1\text{ mod }(p)\). Thus \(1\equiv (x^2)^k\equiv (-1)^k\equiv -1\text{ mod }(p)\), which is impossible since \(p\) is odd, so there can be no solution.
Let \(p=13\), so \(p\equiv 1 \text{ mod }(4)\). Then \(k=6\), and \(6!=720\equiv 5\text{ mod }(13)\), so \(x=5\) is a solution of \(x^2+1\equiv 0 \text{ mod }(13)\), as is easily verified. The other solution is \(-5\equiv 8 \text{ mod }(13)\).
Lagrange’s Theorem implies that if \(p\) is any prime then there are at most two classes \([x]\in{\mathbb Z}_p\) of solutions of \(x^2+1\equiv 0\text{ mod }(p)\). When \(p\equiv 1\text{ mod }(4)\) these are the two classes \(\pm\,[k!]\), when \(p\equiv 3 \text{ mod }(4)\) there are no solutions, and when \(p=2\) there is a unique class \([1]\) of solutions.
Square roots mod \((p)\) continued
Let \(p\equiv 3\) mod \((4)\) be prime and let \(y\) be an integer with \([y]\neq 0\) in \(\mathbb Z_p\). Then exactly one of \([y],[-y]\) has square roots in \(\mathbb Z_p\).
Moreover if \([x]\equiv [y]^{(p+1)/4}\) in \(\mathbb Z_p\) then \([\pm x]\) are the two square roots of \([y]\) or the two square roots of \([-y]\).
Of course if \([y]=[0]\) in \(\mathbb Z_p\) then \([0]\) is the unique square root of \([y]\).
Proof. As \([y]\neq [0]\) we have \(y\) coprime to \(p\) so Fermat’s theorem tells us that \(y^{p-1}\equiv 1\) mod \((p)\). Therefore \[ x^4\equiv y^{p+1}\equiv y^2y^{p-1}\equiv y^2 \text{ mod }(p) \]
Hence \(x^4-y^2\equiv 0\) mod \((p\)). Now factorising we get \((x^2-y)(x^2+y)\equiv 0\) so either \(x^2-y\equiv 0\) mod \((p)\) or \(x^2+y\equiv 0\) mod \((p)\): if say \(x^2-y\not\equiv 0\) mod \((p)\) then \(x^2-y\) is coprime to \(p\) allowing us to cancel this factor giving \(x^2+y\equiv 0\) mod \((p)\).
Hence \([x]^2=[-x]^2=[y]\) or \([x]^2=[-x]^2=[-y]\) Lagrange’s Theorem tells us that (whichever case we are in) the congruence class mod \((p)\) has at most 2 square roots so \([\pm x]\) are the only square roots of this value.
Now suppose that both \([y],[-y]\) have square roots, so \(y\equiv a^2\) and \(-y\equiv b^2\) for some \(a,b\in \mathbb Z\).
Let \(c=ay^{p-2}\) so \(ac=a^2y^{p-2}=y^{p-1}\equiv 1\) mod \((p)\).
Now \[(bc)^2\equiv b^2c^2\equiv -yc^2\equiv -(yc^2)\equiv -(a^2c^2)\equiv-(ac)^2\equiv -1\text{ mod }(p). \] But by Theorem 6.12, \(-1\) has no square roots mod \((p)\) when \(p\equiv 3\) mod \((4)\), giving a contradiction.
Hence exactly one of the pair \([y],[-y]\) has a square root mod \((p)\).
Find the square roots of \(5\) mod \((11)\).
Since \(11\equiv 3\) mod \((4)\), we compute \((p+1)/4=3\), and set \(x\equiv5^3\equiv 4\) mod \((11)\). Now \(4^2=16\equiv 5\) mod \((11)\) so the square roots of \(5\) are \(\pm 4\) mod \((11)\).
Now consider the class \(2\) mod \((11)\). Carrying out the above calculation we see that if \(2\) has any square roots they are \(\pm 2^3\equiv 8\) mod \((11)\). However \(8^2=64\equiv 9\equiv -2\) mod \((11)\), so \(2\) has no square roots mod \((11)\).
Square roots mod \((pq)\)
Suppose we want to find the square roots of \(71\) mod \((77)\). Factorising \(77=7*11\) we notice that if \(x^2\equiv 71\) mod \((77)\), then \(x^2\equiv 71\) mod \((7)\) and \(x^2\equiv 71\) mod \((11)\), so we have \(x^2\equiv 1\) mod \((7)\) and \(x^2\equiv 5\) mod \((11)\). Applying the proposition we see that \(x\equiv \pm 1\) mod \((7)\) and \(x\equiv \pm 4\) mod \((11)\).
Now we know from the Chinese remainder theorem that a congruence mod \((7)\) and another mod \((11)\) can be recombined to give us a congruence mod \((77)\), so combining these congruences in the four possible ways we obtain four square roots for \(71\) mod \((77)\). For example taking the congruences \(x\equiv 1\) mod \((7)\) and \(x\equiv 4\) mod \((11)\) we get \(x\equiv 15\) mod \((77)\).
Solving all four systems we can recombine to get \[ x\equiv \pm 15 , \pm 29 \text{ mod }(77). \]
Hence we have found the four square roots of \(71\) mod \((77)\).
Observations
We solve the 4 pairs of linear congruences
- \(x\equiv1\text{ mod }7, x\equiv4\text{ mod }11\),
- \(x\equiv1\text{ mod }7, x\equiv-4\text{ mod }11\),
- \(x\equiv-1\text{ mod }7, x\equiv4\text{ mod }11\),
- \(x\equiv-1\text{ mod }7, x\equiv-4\text{ mod }11\).
But notice that if we put \(y=-x\) in (3) then we get \(y\equiv1\text{ mod }7, y\equiv-4\text{ mod }11\), which we have already solved in (2). So the solution to (3) is just the negative of the solution to (2). Similarly, the solution to (4) is just the negative to the solution for (1).
Notice that \(29\equiv 15\text{ mod }7\) and \(29\equiv-15\text{ mod }11\), but \(29\not\equiv15\text{ mod }11\) and \(29\not\equiv-15\text{ mod }7\). This always happens (providing we are not trying to calculate the square root of a multiple of \(p\) or \(q\)). To see this, suppose that in general, we start with the congruence \(x^2\equiv y\text{ mod }pq\), which then leads to the 4 linear pairs of congruences
- \(x\equiv c\text{ mod }p, x\equiv d\text{ mod }q\), with solution \(x\equiv a\text{ mod }pq\),
- \(x\equiv c\text{ mod }p, x\equiv-d\text{ mod }q\), with solution \(x\equiv b\text{ mod }pq\),
- \(x\equiv-c\text{ mod }p, x\equiv d\text{ mod }q\), with solution \(x\equiv -b\text{ mod }pq\),
- \(x\equiv-c\text{ mod }p, x\equiv-d\text{ mod }q\), with solution \(x\equiv -a\text{ mod }pq\).
Now, \(a\equiv c\text{ mod }p\) and \(b\equiv c\text{ mod }p\) and so \(a\equiv b\text{ mod }p\). In a similar way we can see that \(a\equiv d\equiv -b\text{ mod }q\) (use (1) & (3)). However, \(a\not\equiv-b\text{ mod }p\) since we could then deduce that \(b\equiv-b\text { mod }p\) which would mean that \(p|2b\) and so either \(p|2\) or \(p|b\). But \(p\) is an odd prime so can’t divide 2 and if \(p|b\) then \(b\equiv0\text{ mod }p\) meaning that \(c\equiv b\equiv0\text{ mod }p\). But then \(y\equiv0\text{ mod }p\), a contradiction. In a similar way, \(a\not\equiv b\text{ mod q}\).
Factorising via square roots
Suppose that \(n=pq\) is a product of two primes and we know the four solutions \(x\equiv \pm a, \pm b\) to the congruence \(x^2\equiv y\) mod \((n)\) (assuming that \(y\) has a square root mod \(n\)).
From the previous discussion we know that \(a\equiv b\) mod \((p)\) and \(a\not\equiv b\) mod \((q)\) (and \(a\equiv -b\) mod \((q)\) and \(a\not\equiv -b\) mod \((p)\)) - or the same congruences with \(p,q\) interchanged - so that \(p|(a-b)\) but \(q\nmid(a-b)\). It follows that \(\gcd(a-b, n)=p\). Applying the Euclidean algorithm we can therefore extract one of the two factors of \(n\).
In the previous example we found the roots \(15^2\equiv 29^2\equiv 71\text{ mod }(77)\).
Hence \(7=\gcd(15-29, 77)\) is a factor of \(77\).
An important principle
All of the calculations we have just done can be done quickly and efficiently (Euclidean algorithm, Chinese remainder Theorem, extracting roots) except factorising \(n\). Hence we conclude:
If \(n\) is the product of two primes and \(y\) is an integer coprime to \(n\) which has a square root mod \((n)\), then finding the four square roots of \(y\) is computationally equivalent to factorising \(n\).
In other words if we can factorise \(n\) then we can compute the roots, and if we can compute the roots then we can factorise \(n\).
Square Roots and round coins
We finish the section on square roots with a surprising application.
A story: Alex and Bob are convicts in a high security jail. They have adjacent cells and can talk to one another but cannot see or otherwise contact one another. They both want to read “Escape from Colditz” but the library trolley has only one copy and they can’t decide who will get to read it first. I know says Alex “Let’s toss a coin!” Alright says Bob fishing a coin out of his pocket and throwing it high into the air. As it lands Alex shouts heads. Sorry says Bob it was tails. There is a silence, then Alex says “Are you sure?” \(\ldots\)
The question is, can we make a fair coin tossing scheme to use in this situation.
The answer is yes, and it uses a technique which relies on the facts we have just proved concerning square roots and factorisation.
Virtual coin tossing
Alex chooses two large random primes, both congruent to \(3\) mod \((4)\). (S)he keeps them secret but tells Bob the product \(n=pq\). Bob of course, without access to a large computer has no hope of factorising \(n\).
Bob chooses a random integer \(x\) and computes \(y=x^2\) mod \((n)\). He keeps \(x\) secret but tells Alex what \(y\) is. Alex, knowing the factorisation of \(n\) can compute the four possible roots \(\pm a, \pm b\) of \(y\). One of these will be \(x\) but (s)he doesn’t know which.
Alex chooses one of the pairs, either \(\pm a\) or \(\pm b\) and calls out the result to Bob. Suppose that Alex calls out \(\pm a\).
If \(x=\pm b\) then Bob tells Alex that Alex has lost. If \(x=\pm a\) then Bob tells Alex that Alex has won.
Clearly Alex will win with probability \(1/2\) just as in a traditional coin toss.
But why can’t Bob cheat?
Suppose that Alex really loses because \(\pm a\not\equiv \pm x\). Then Bob now knows all four roots of \(y\), namely \(\pm a\) and \(\pm x\). Hence he can find a prime factor of \(n\) as we discussed above. So Alex can verify that Bob is not cheating by asking him to give him one of the prime factors!
Alex chooses \[p=2038074743, q=1190494759\]
(S)he sends \[n=pq=2426317299991771937\] to Bob. Bob takes \[x=141213562373095048\]
and computes \[y\equiv x^2\equiv363278601055491705 \text{ mod } (n)\] which he tells Alex.
Alex computes
\[ y^{(p+1)/4}\equiv 1701899961 \text{ mod } (p) \text{ and } y^{(q+1)/4}\equiv 325656728 \text{ mod } (q)\]
The Chinese remainder theorem combines these in four ways to give
\[a\equiv \pm 1012103737618676889, b\equiv\pm 937850352623334103 \text{ mod } (n)\]
Suppose Alex sends 1012103737618676889 to Bob. Then, as this is \(-x\) mod \((n)\). Bob declares Alex the winner. If Alex sends 937850352623334103 to Bob then Bob declares Alex the loser and computes
\[\gcd(141213562373095048-937850352623334103, n)= 1190494759\] as proof that he did not cheat!