View Single Post
 2017-02-22, 13:08 #1 Nick     Dec 2012 The Netherlands 31768 Posts Basic Number Theory 18: quadratic equations modulo n Take any real numbers $$a,b,c$$ with $$a\neq 0$$, and suppose we wish to find all real numbers $$x$$ for which $$ax^2+bx+c=0$$. As $$a\neq 0$$, we can divide by it throughout, getting $$x^2+\frac{b}{a}x+\frac{c}{a}=0$$. In other words, the values of $$x$$ satisfying this equation are the same as those satisfying the original one. We now use a trick known as completing the square: if we add $$\left(\frac{b}{2a}\right)^2$$ to both sides of the equation, they remain equal so $x^2+\frac{b}{a}x+\left(\frac{b}{2a}\right)^2+\frac{c}{a}= \left(\frac{b}{2a}\right)^2.$ The point of this is that the first 3 terms on the left are now what we get if we multiply out the bracket in $$\left(x+\frac{b}{2a}\right)^2$$, so we may write the equation as $\left(x+\frac{b}{2a}\right)^2+\frac{c}{a}=\left(\frac{b}{2a}\right)^2.$ Now that $$x$$ only appears once, it is not difficult to write it in terms of $$a,b$$ and $$c$$: we have $\left(x+\frac{b}{2a}\right)^2=\left(\frac{b}{2a}\right)^2-\frac{c}{a} =\frac{b^2-4ac}{4a^2}$ so $x+\frac{b}{2a}=\pm\sqrt{\frac{b^2-4ac}{4a^2}} =\frac{\pm\sqrt{b^2-4ac}}{2a}$ hence $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$ which is the familiar formula for the solutions of the quadratic equation we started with. The number $$b^2-4ac$$ is called the discriminant of the polynomial $$ax^2+bx+c$$. If it is positive, then there are 2 distinct values of $$x$$ satisfying the equation. If it is zero, then there is just 1 value for $$x$$, and if it is negative then there are no real values for $$x$$ (just 2 complex ones). Now let $$n$$ be a positive integer and $$a,b,c$$ integers with $$a\not\equiv 0\pmod{n}$$, and suppose we wish to find all integers $$x$$ for which $$ax^2+bx+c\equiv 0\pmod{n}$$. We cannot simply use the above formula: while addition, subtraction and multiplication in the integers modulo $$n$$ obey all the usual rules of arithmetic, we cannot always divide by $$2a$$ (or even by 2 if $$n$$ is even) let alone take a square root. In theory, we could simply try each value of $$x$$ from 0 to $$n-1$$ inclusive in turn, but that is not very efficient unless $$n$$ is quite small. Instead, we need to understand the units and quadratic residues in the integers modulo $$n$$. Fortunately, we have already done most of the work - all that remains is to determine which units are squares modulo a prime power, and then we shall be able to tackle the problem systematically. As usual, we have to treat the prime number 2 separately. Proposition 105 Let $$p$$ be an odd prime number and $$m$$ a positive integer. Then, for any integer $$a$$ not divisible by $$p$$, $$\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*$$ is a square if and only if $$\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^*$$ is a square. proof By proposition 95, the unit group $$(\mathbb{Z}/p^m\mathbb{Z})^*$$ of the integers modulo $$p^m$$ is cyclic, so there exists an integer $$d$$ such that $\left(\mathbb{Z}/p^m\mathbb{Z}\right)^* =\{\bar{d}^0=\bar{1},\bar{d}^1=\bar{a}, \bar{d}^2,\bar{d}^3,\ldots, \bar{d}^{(p-1)p^{m-1}-1}\}$ with $$\bar{d}^{(p-1)p^{m-1}}=\bar{1}$$. As $$p$$ is odd (and $$m\geq 1$$), this is a cylic group of even order so, by proposition 86, the powers of $$\bar{d}^2$$ form a cyclic subgroup containing exactly half of the elements, and these are precisely the squares in $$(\mathbb{Z}/p^m\mathbb{Z})^*$$. Let $$f:(\mathbb{Z}/p^m\mathbb{Z})^*\rightarrow (\mathbb{Z}/p\mathbb{Z})^*$$ be the function sending $$\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^*$$ to $$\bar{n}\in (\mathbb{Z}/p\mathbb{Z})^*$$ (equivalently, $$f(n\bmod{p^m})=n\bmod{p}$$). We must check that this is well-defined. For any integer $$n$$, if $$n\bmod{p^m}$$ is a unit in the integers modulo $$p^m$$ then $$\gcd(n,p^m)=1$$ so $$\gcd(n,p)=1$$ as well, hence $$n\bmod{p}$$ is a unit in the integers modulo $$p$$. And, for any integers $$m,n$$, if $$\bar{m}=\bar{n}\in(\mathbb{Z}/p^m\mathbb{Z})^*$$ then $$p^m$$ divides $$m-n$$ so $$p$$ divides $$m-n$$ too, and therefore $$\bar{m}=\bar{n}\in(\mathbb{Z}/p\mathbb{Z})^*$$. Thus $$f$$ is well-defined. Conversely, for any integer $$n$$, if $$n\bmod{p}$$ is a unit in the integers modulo $$p$$ then $$\gcd(n,p)=1$$ so $$\gcd(n,p^m)=1$$ and $$n\bmod{p^m}$$ is a unit in the integers modulo $$p^m$$. Hence $$f$$ is surjective. Moreover, for any integer $$n$$, $$f(\bar{d}^n)=(f(\bar{d}))^n$$ so $$f(\bar{d})$$ generates the whole cyclic group $$(\mathbb{Z}/p\mathbb{Z})^*$$. In the same way as before, the powers of $$f(\bar{d})^2$$ form a cyclic subgroup containing exactly half the elements, and these are precisely the squares in $$(\mathbb{Z}/p\mathbb{Z})^*$$. Thus $$f$$ maps squares in $$(\mathbb{Z}/p^m\mathbb{Z})^*$$ to squares in $$(\mathbb{Z}/p\mathbb{Z})^*$$, and non-squares to non-squares. It follows that, for any integer $$a$$ not divisible by $$p$$, $$\bar{a}\in\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*$$ is a square if and only if $$\bar{a}\in\left(\mathbb{Z}/p\mathbb{Z}\right)^*$$ is a square. ∎ Proposition 106 Let $$a,m$$ be integers such that $$a$$ is odd and $$m\geq 3$$. Then $$\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^*$$ is a square if and only if $$a\equiv 1\pmod{8}$$. proof By proposition 96, $\left(\mathbb{Z}/2^m\mathbb{Z}\right)^*= \{(-\bar{1})^i\bar{5}^j:i,j\in\mathbb{Z}\}$ and, for all integers $$i,j,k,l$$, $(-\bar{1})^i\bar{5}^j=(-\bar{1})^{k}\bar{5}^{l}\Leftrightarrow 2|i-k\mbox{ and }2^{m-2}|j-l.$ Suppose $$a\equiv 1\pmod{8}$$. We have $$a\equiv (-1)^r5^s\pmod{2^m}$$ for some integers $$r,s$$, and $$m\geq 3$$ so $$(-1)^r5^s\equiv 1\pmod{8}$$. As $$5^2\equiv 1\pmod{8}$$ but $$\pm5\not\equiv 1\pmod{8}$$, it follows that $$r$$ and $$s$$ are both even, making $$\bar{a}\in\left(\mathbb{Z}/2^m\mathbb{Z}\right)^*$$ a square. Suppose instead that $$\bar{a}$$ is a square. Then there exist integers $$i,j$$ such that $$((-1)^i5^j)^2\equiv a\pmod{2^m}$$. And $$m\geq 3$$ so $$a\equiv (-1)^{2i}5^{2j}\equiv 1\pmod{8}$$. ∎ Before we can tackle quadratic equations modulo $$n$$, we need to be able to solve linear equations and determine the existence of square roots. LINEAR EQUATIONS Let $$n$$ be a positive integer, $$a,b$$ integers with $$a\not\equiv 0\pmod{n}$$ and suppose we wish to find all integers $$x$$ such that $ax+b\equiv 0\pmod{n}.$ Let $$d=\gcd(a,n)$$. If $$d=1$$ then there exists an integer $$u$$ such that $$au\equiv 1\pmod{n}$$ (which can be found with the Euclidean algorithm) so $$ax+b\equiv 0\pmod{n}$$ if and only if $$x\equiv -bu\pmod{n}$$. Suppose $$d>1$$. Then $$a=da'$$ and $$n=dn'$$ for some integers $$a',n'$$. If there exists an integer $$x$$ with $$ax+b\equiv 0\pmod{n}$$ then $$b\equiv -da'x\pmod{dn'}$$ so $$d|b$$. Thus is $$b$$ is not divisible by $$d$$ then there are no solutions. If $$b$$ is divisible by $$d$$ then $$b=db'$$ for some integer $$b'$$ and, for all integers $$x$$, $$ax+b\equiv 0\pmod{n}$$ if and only if $$a'x+b'\equiv 0\pmod{n'}$$. Moreover, $$\gcd(a',n')=1$$, so we can proceed as in the first case. EXISTENCE OF SQUARE ROOTS Let $$n$$ be a positive integer, $$c$$ an integer and suppose we wish to determine whether an integer $$x$$ exists such that $$x^2\equiv c\pmod{n}$$. Let $$d=\gcd(c,n)$$, and suppose first that $$d=1$$. We assume that $$n$$ is small enough to be factorized completely: write $$n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}$$ where $$k$$ is a non-negative integer, $$p_1,p_2,\ldots,p_k$$ are distinct prime numbers and $$e_1,e_2,\ldots,e_k$$ are positive integers. By the Chinese Remainder Theorem, there exists an integer $$x$$ such that $$x^2\equiv c\pmod{n}$$ if and only if, for each $$i\in\{1,2,\ldots,k\}$$, there exists an integer $$x_i$$ with $$x_i^2\equiv c\pmod{p_i^{e_i}}$$ (and the possible values of $$x$$ can then be constructed from all combinations of $$x_1,x_2,\ldots,x_k$$). Take any $$i\in\{1,2,\ldots,k\}$$. If $$p_i\neq 2$$ then $$c$$ is a square modulo $$p_i^{e_i}$$ if and only if $$c$$ is a square modulo $$p_i$$ by proposition 105, and $$p_i$$ does not divide $$c$$ (since $$d=1$$) so this holds if and only if $$(\frac{c}{p_i})=1$$, which we can determine using the quadratic reciprocity law (corollary 104). Suppose instead $$p_i=2$$. If $$e_i=1$$ then $$c$$ is a square modulo 2. If $$e_i=2$$ then $$c$$ is a square modulo 4 if and only if $$c\equiv 1\pmod{4}$$ (in this case, $$n$$ is even so $$c$$ is odd). And if $$e_i\geq 3$$ then $$c$$ is a square modulo $$2^{e_i}$$ if and only if $$c\equiv 1\pmod{8}$$ by proposition 106. This covers all cases where $$d=1$$. Now suppose that $$d>1$$. Write $$d=r^2s$$ where $$r,s$$ are integers with $$r$$ as large as possible. In other words, $$s$$ is a product of distinct prime numbers, namely those occurring to an odd power in the prime factorization of $$d$$. Thus $$s$$ is not divisible by the square of any number greater than 1 - we call s square-free. There exist integers $$c',n'$$ such that $$c=dc'$$ and $$n=dn'$$. For any integer $$x$$, if $$x^2\equiv c\pmod{n}$$ then $$r^2s|x^2$$ and $$s$$ is square-free so $$rs|x$$. Thus $$x=rsy$$ for some integer $$y$$ and $$(rsy)^2\equiv r^2sc'\pmod{r^2sn'}$$ so $$sy^2\equiv c'\pmod{n'}$$. Any prime number dividing both $$s$$ and $$n'$$ also divides $$c'$$, but $$\gcd(c',n')=1$$ so $$\gcd(s,n')=1$$ too and therefore there exists an integer $$u$$ with $$su\equiv 1\pmod{n'}$$. Thus $$y^2\equiv c'u\pmod{n'}$$, and $$\gcd(c'u,n')=1$$ so we can proceed as in the case where $$d=1$$. Note that the above determines whether a square root of $$c$$ exists in the integers modulo $$n$$, but not how to find it. General solutions to this problem use mathematics that we have not yet covered. For small powers of small primes, however, trial and error will suffice, and there are other special cases in which it is straightforward as well (see exercises 83 and 86 below). QUADRATIC EQUATIONS Let $$n$$ be a positive integer and $$a,b,c$$ integers with $$a\not\equiv 0\pmod{n}$$, and suppose we wish to find all integers $$x$$ for which $ax^2+bx+c\equiv 0\pmod{n}.$ We cannot necessarily divide by $$a$$ to complete the square, so we multiply throughout by $$4a$$ instead, getting $$4a^2x^2+4abx+4ac\equiv 0\pmod{4an}$$, and write this as a square: $(2ax+b)^2\equiv b^2-4ac\pmod{4an}.$ Using the above method for square roots, we may determine whether $$b^2-4ac$$ is a square in the integers modulo $$4an$$ and, if so, we can take each integer $$y$$ with $$y^2\equiv b^2-4ac\pmod{4an}$$ and use the above method for linear equations to solve $$2ax+b\equiv y\pmod{4an}$$. Exercises 83. Let $$p$$ be a prime number with $$p\equiv 3\pmod{4}$$, $$c$$ an integer which is a square modulo $$p$$, and $$x\equiv c^{\frac{p+1}{4}}\pmod{p}$$. Show that $$x^2\equiv c\pmod{p}$$. 84. Find all integers $$x$$ such that $$12x+24\equiv 0\pmod{33}$$. 85. Find all integers $$x$$ such that $$3x^2+6x+5\equiv 0\pmod{7}$$. 86. Let $$p$$ be a prime number with $$p\equiv 5\pmod{8}$$ and $$c$$ an integer which is a square modulo $$p$$. Let $$x,y$$ be integers such that $$x\equiv c^{\frac{p+3}{8}}\pmod{p}$$ and $$y\equiv 2^{\frac{p-1}{4}}\pmod{p}$$. Show that $$x^2\equiv\pm c\pmod{p}$$ and $$y^2\equiv -1\pmod{p}$$. Conclude that $$x$$ or $$xy$$ is a square root of $$c$$ modulo $$p$$.