Chapter 5 Congruences with a prime modulus
We met an example in the last chapter, where a single congruence \(\text{mod }(n)\) is equivalent to a set of simultaneous congruences modulo the prime powers \(p^e\) appearing in the factorisation of \(n\). In this chapter we will study congruences \(\text{mod }(p)\), where \(p\) is prime. In this case we shall see that in addition to modular addition, subtraction and multiplication, cancellation works more smoothly.
The arithmetic of \({\mathbb Z}_p\)
We saw in Corollary 4.29 that a linear congruence \(ax\equiv b\text{ mod }(n)\) has a unique solution \(\text{mod }(n)\) if \(\gcd(a,n)=1\). Now if \(n\) is a prime \(p\), then \(\gcd(a,n)=\gcd(a,p)\) is either \(1\) or \(p\). In the former case, we have a unique solution \(\text{mod }(p)\), while in the latter case either every \(x\) is a solution (when \(p\,|\,b\)) or no \(x\) is a solution (when \(p\nmid\;b\)).
Looking at this from another point of view, the polynomial \(ax-b\) of degree \(d=1\) over \({\mathbb Z}_p\) (\(a\text{ or }b\not\equiv 0\text{ mod }(p)\)), then it has at most one root in \({\mathbb Z}_p\). Now in the Linear Algebra module, we learn that a non-trivial polynomial of degree \(d\), with real or complex coefficients, has at most \(d\) distinct roots in \({\mathbb R}\) or \({\mathbb C}\). Our first main theorem, due to Lagrange, states that this is also true for the number system \({\mathbb Z}_p\).
Let \(p\) be prime, and let \(f(x)=a_dx^d+\cdots+a_1x+a_0\) be a polynomial with integer coefficients, where \(a_i\not\equiv 0\text{ mod }(p)\) for some \(i\). Then the congruence \(f(x)\equiv 0\text{ mod }(p)\) is satisfied by at most \(d\) congruence classes \([x]\in{\mathbb Z}_p\).
- Note that we allow the possibility that \(a_d\equiv0\), so that \(f(x)\) has degree less than \(d\).
- Even if \(a_d\not\equiv 0\), \(f(x)\) may still have fewer than \(d\) roots in \({\mathbb Z}_p\). For example, \(f(x)=x^2+1\) has only one root in \({\mathbb Z}_2\), namely the class \([1]\), and it has no roots in \({\mathbb Z}_3\).
- The condition that \(a_i\not\equiv 0\) for some \(i\) ensures that \(f(x)\) yields a non-trivial polynomial when we reduce it \(\text{mod }(p)\). If \(a_i\equiv 0\) for all \(i\) then all \(p\) classes \([x]\in{\mathbb Z}_p\) satisfy \(f(x)\equiv 0\), so the result will fail if \(d<p\).
- If \(p\) is not prime the polynomial may have more than \(d\) roots. For example, the polynomial \(f(x)=x^2-1\), of degree \(d=2\), has four roots in \({\mathbb Z}_8\), namely the classes \([1], [3], [5]\) and \([7]\).
Proof. We use induction on \(d\). If \(d=0\) then \(f(x)=a_0\) with \(p\) not dividing \(a_0\), so there are no solutions of \(f(x)\equiv 0\), as required. For the inductive step, we now assume that \(d\geq 1\), and that all polynomials \(g(x)=b_{d-1}x^{d-1}+\cdots+b_0\) with some \(b_i\not\equiv 0\) have at most \(d-1\) roots \([x]\in{\mathbb Z}_p\).
If the congruence \(f(x)\equiv 0\) has no solutions, there is nothing left to prove, so suppose that \([a]\) is a solution; thus \(f(a)\equiv 0\), so \(p\) divides \(f(a)\). Now \[f(x)-f(a)=\sum_{i=0}^da_ix^i-\sum_{i=0}^da_ia^i=\sum_{i=0}^da_i(x^i-a^i) =\sum_{i=1}^da_i(x^i-a^i)\,.\] For each \(i=2, \ldots, d\) we can put \[x^i-a^i=(x-a)(x^{i-1}+ax^{i-2}+\cdots+a^{i-2}x+a^{i-1})\,.\] By taking out the common factor \(x-a\) we have \[f(x)-f(a)=(x-a)g(x)\] for some polynomial \(g(x)\) with integer coefficients, of degree at most \(d-1\). Now \(p\) cannot divide all the coefficients of \(g(x)\): if it did, then since it also divides \(f(a)\), it would have to divide all the coefficients of \(f(x)=f(a)+(x-a)g(x)\), against our assumption. We may therefore apply the induction hypothesis to \(g(x)\), so that at most \(d-1\) classes \([x]\) satisfy \(g(x)\equiv 0\).
We now count classes \([x]\) satisfying \(f(x)\equiv 0\): if any class \([x]=[b]\) satisfies \(f(b)\equiv 0\), then \(p\) divides both \(f(a)\) and \(f(b)\), so it divides \(f(b)-f(a)=(b-a)g(b)\); since \(p\) is prime \(p\) divides \(b-a\) or \(g(b)\), so either \([b]=[a]\) or \(g(b)\equiv 0\). There are at most \(d-1\) classes \([b]\) satisfying \(g(b)\equiv 0\), and hence at most \(1+(d-1)=d\) satisfying \(f(b)\equiv 0\), as required.
Find the roots of the polynomial \(f(x)=x^2+1\) in \({\mathbb Z}_p\) for each prime \(p\leq 17\). Make a conjecture about how many roots \(f(x)\) has in \({\mathbb Z}_p\) for each prime \(p\).
We shall revisit this exercise shortly.
Let \(f(x)=a_dx^d+\cdots+a_1x+a_0\) be a polynomial with integer coefficients, and let \(p\) be prime. If \(f(x)\) has more than \(d\) roots in \({\mathbb Z}_p\), then each coefficient \(a_i\equiv 0\text{ mod }p\).
Polynomials of high degree
Lagrange’s Theorem tells us nothing new about polynomials \(f(x)\) of degree \(d\geq p\): there are only \(p\) classes in \({\mathbb Z}_p\), so it is trivial that at most \(d\) classes satisfy \(f(x)\equiv 0\).
The following result, useful in studying polynomials of high degree, is known as Fermat’s Little Theorem (not to be confused with Fermat’s Last Theorem).
If \(p\) is prime and \(a\not\equiv 0\text{ mod }(p)\), then \(a^{p-1}\equiv 1\text{ mod }(p)\).
We give Proof B from (Jones and Jones 2006), which is purely number-theoretic.
Proof. The integers \(1, 2, \ldots, p-1\) form a complete set of non-zero residues \(\text{mod }(p)\). If \(a\not\equiv 0\text{ mod }(p)\) then \(xa\equiv ya\) implies \(x\equiv y\), by Corollary 4.29, so that the integers \(a, 2a, \ldots, (p-1)a\) lie in distinct classes \(\text{mod }(p)\). None of these integers is divisible by \(p\), so they also form a complete set of non-zero residues.
It follows that \(a, 2a, \ldots, (p-1)a\) are congruent to \(1, 2, \ldots, p-1\) in some order. (For instance, if \(p=5\) and \(a=3\) then multiplying the residues \(1, 2, 3, 4\) by \(3\) we get \(3, 6, 9, 12\), which are respectively congruent to \(3, 1, 4, 2\).) The products of these two sets of integers must therefore lie in the same class, that is, \[1\times 2\times \cdots\times (p-1)\equiv a\times 2a\times \cdots\times (p-1)a\;\;\text{ mod }(p)\,,\] or equivalently \[(p-1)!\equiv (p-1)!\,a^{p-1}\;\;\text{ mod }(p)\,.\] Rearranging, we get \[ (p-1)!\left(1-a^{p-1}\right)\equiv0\text{ mod }p \] so since \(p\) and \((p-1)!\) are coprime, then we see from Lemma 4.31 (2) that \(1\equiv a^{p-1}\text{ mod }p\).
Theorem 5.4 states that all the classes in \({\mathbb Z}_p\) except \([0]\) are roots of the polynomial \(x^{p-1}-1\).
If \(p\) is prime then \(a^p\equiv a\text{ mod }(p)\) for every integer \(a\).
Proof. If \(a\not\equiv 0\) then Theorem 5.4 gives \(a^{p-1}\equiv 1\), so multiplying each side by \(a\) gives the result. If \(a\equiv 0\) then \(a^p\equiv 0\) also, so the result is again true.
Since \(23\) is prime and \(3\) is not divisible by \(23\), we can apply Theorem 5.4 with \(p=23\) and \(a=3\), so that \(3^{22}\equiv 1\text{ mod }(23)\). Now \(67=22\times 3+1\), so \[3^{67}=(3^{22})^3\times 3^{1}\equiv 1^3\times 3^{1}\equiv 3^{1}=3\text{ mod }(23)\,.\]
Show that \(a^{25}-a\) is divisible by \(30\) for every integer \(a\).
Here Corollary 5.5 is more appropriate, since it refers to all integers \(a\), rather than just those coprime to \(p\). By factorising \(30\), we see that it is sufficient to prove that \(a^{25}-a\) is divisible by each of the primes \(p=2, 3\) and \(5\). Remember that \(p|a^{25}-a\) if and only if \(a^{25}-a\equiv0\text{ mod }p\) if and only if \(a^{25}\equiv a\text{ mod }p\).
Let us deal with \(p=5\) first. Applying Corollary 5.5 twice, we have \[a^{25}=(a^5)^5\equiv a^5\equiv a\;\;\text{ mod }(5)\,,\] so \(5\) divides \(a^{25}-a\) for all \(a\). Similarly \(a^3\equiv a\text{ mod }(3)\), so \[a^{25}=(a^3)^8a\equiv a^8a=a^9=(a^3)^3\equiv a^3\equiv a\;\;\text{ mod }(3)\,,\] as required.
For \(p=2\) a direct argument easily shows that \(a^{25}-a\) is always even, but we can also continue with this method and use \(a^2\equiv a \text{ mod }(2)\) to deduce (rather laboriously) that \[a^{25}=(a^2)^{12}a\equiv a^{12}a=(a^2)^6a=a^6a=\] \[(a^2)^3a\equiv a^3a=a^4=(a^2)^2\equiv a^2\equiv a\;\;\text{ mod }(2)\,.\]
Find the least non-negative residue of \(3^{91}\text{ mod }(23)\).
Corollary 5.5 shows that if \(f(x)\) is any polynomial of degree \(d\geq p\), then by repeatedly replacing any occurrence of \(x^p\) with \(x\) we can find a polynomial \(g(x)\) of degree less than \(p\) with the property that \(f(x)\equiv g(x)\) for all integers \(x\). In other words, when considering polynomials \(\text{mod }(p)\), it is sufficient to restrict attention to those of degree \(d<p\). Similarly, the coefficients can also be simplified by reducing them \(\text{mod }(p)\).
Let us find all the roots of the congruence \[f(x)=x^{17}+6x^{14}+2x^5+1\equiv 0\;\;\text{ mod }(5)\,.\]
Here \(p=5\), so by replacing \(x^5\) with \(x\) we can replace the leading term \(x^{17}=(x^5)^3x^2\) with \(x^3x^2=x^5\), and hence with \(x\). Similarly \(x^{14}\) is replaced with \(x^2\), and \(x^5\) with \(x\), so giving the polynomial \(x+6x^2+2x+1\). Reducing the coefficients \(\text{mod }(5)\) gives \(x^2+3x+1\). Thus \(f(x)\equiv 0\) is equivalent to the much simpler congruence \[g(x)=x^2+3x+1\equiv 0\;\;\text{ mod }(5)\,.\]
Here we can simply try all five classes \([x]\in{\mathbb Z}_5\), or else note that \(g(x)\equiv(x-1)^2\); either way, we find that \([x]=[1]\) is the only root of \(g(x)\equiv 0\), so this class is the only root of \(f(x)\equiv 0\).
As another application of Fermat’s Little Theorem, we prove a result known as Wilson’s Theorem, though it was first proved by Lagrange in 1770:
An integer \(n>1\) is prime if and only if \((n-1)!\equiv-1\text{ mod }(n)\).
Proof. Suppose that \(n\) is a prime \(p\). If \(p=2\) then \((p-1)!=1\equiv -1\text{ mod }(p)\), as required, so we may assume that \(p\) is odd. Define \[f(x)=(1-x)(2-x)\ldots(p-1-x)+1-x^{p-1}\,,\] a polynomial with integer coefficients. This has degree \(d<p-1\), since when the product is expanded, the two terms in \(f(x)\) involving \(x^{p-1}\) cancel. If \(a=1, 2, \ldots, p-1\) then \(f(a)\equiv 0\text{ mod }(p)\): the product \((1-a)(2-a)\ldots(p-1-a)\) vanishes since it has a factor equal to \(0\), and \(1-a^{p-1}\equiv 0\) by Fermat’s Little Theorem.
Thus \(f(x)\) has more than \(d\) roots \(\text{mod }(p)\), so by Corollary 5.3 its coefficients are all congruent to \(0\) mod \(p\). In particular, the constant term \((p-1)!+1\equiv0\text{ mod }p\), so \((p-1)!\equiv -1\).
For the converse, suppose that \((n-1)!\equiv -1\text{ mod }(n)\). We then have \((n-1)!\equiv -1\text{ mod }(m)\) for any factor \(m\) of \(n\). If \(m<n\) then \(m\) appears as a factor of \((n-1)!\), so \((n-1)!\equiv 0\text{ mod }(m)\) and hence \(-1\equiv 0\text{ mod }(m)\). This implies that \(m=1\), so we conclude that \(n\) has no proper factors and is therefore prime.
In principle Wilson’s theorem gives a method for checking whether or not a number is prime, but in practice it is infeasible for large numbers. The run time of an algorithm based on the theorem (or the storage requirement if it is parallelised) grows very fast with the size of \(n\).
In 2003 the Indian mathematician Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal announced that they had discovered an efficient algorithm for deterministic primality testing. Their paper is only 9 pages long and you can read about it on the web at http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
Use Euclid’s theorem and Wilson’s theorem to evaluate\[\gcd(29!+29,30!+29).\]
Recall from Exercise 5.2 we saw that the polynomial \(x^2+1\) in \(\mathbb Z_p\) has roots: \[ \begin{array}{r|l} p&\text{roots}\\\hline 2&1\\ 3&\\ 5&2\text{ and }3\\ 7&\\ 11&\\ 13&5\text{ and }8\\ 17&4\text{ and }13\\ \end{array} \]
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.
If \(x\) and \(y\) are integers and if \(xy\equiv1\mod n\) then we say that \(x\) (and \(y\)) is a unit in \(\mathbb Z_n\). We can think of \(y\) as a multiplicative inverse for \(x\) in \(\mathbb Z_n\).
In particular, if \(p\) is a prime and if \(x\not\equiv 0\mod p\) then Bezout’s Lemma implies that there exist integers \(u,v\) such that \[ xu+pv=1. \] But then \(xu\equiv1\mod p\) and so every integer coprime to \(p\) is a unit in \(\mathbb Z_p\).
Square roots mod \((p)\) continued
Let \(p\equiv 3\) mod \((4)\) be prime and let \(y\) be an integer. Let \(x\equiv y^{(p+1)/4}\) mod \((p)\).
- If \(y\) has a square root mod \((p)\), then the square roots of \(y\) mod \((p)\) are \(\pm x\), and if \(y\not\equiv0\text{ mod }p\) then \(-y\) has no square root.
- If \(y\) has no square roots mod \((p)\) then \(-y\) has a square root mod \((p)\) and the square roots of \(-y\) are \(\pm x\).
Proof. If \(y\equiv 0\) mod \((p)\) then the statements are trivial, so assume that \(y\) is a unit mod \((p)\). 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)\), so at least one of \(\pm y\) has a square root.
Suppose they both have square roots \(y\equiv a^2\) and \(-y\equiv b^2\). Since \(y\) is a unit, so is \(a\), so it has a multiplicative inverse, \(c\) such that \(ac\equiv 1\). Now consider \[(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 5.12, \(-1\) has no square roots mod \((p)\) when \(p\equiv 3\) mod \((4)\). Hence exactly one of the pair \(\pm y\) has a square root mod \((p)\).
Finally it is clear that if \(x\) is a root of \(\pm y\) then so is \(-x\) and Lagrange’s Theorem tells us that there are at most 2 root and so \(\pm x\) are both root.
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!