20170222, 13:08  #1 
Dec 2012
The Netherlands
5×331 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^24ac}{4a^2} \] so \[x+\frac{b}{2a}=\pm\sqrt{\frac{b^24ac}{4a^2}} =\frac{\pm\sqrt{b^24ac}}{2a} \] hence \[x=\frac{b\pm\sqrt{b^24ac}}{2a} \] which is the familiar formula for the solutions of the quadratic equation we started with. The number \(b^24ac\) 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 \(n1\) 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}^{(p1)p^{m1}1}\} \] with \(\bar{d}^{(p1)p^{m1}}=\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 welldefined. 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 \(mn\) so \(p\) divides \(mn\) too, and therefore \(\bar{m}=\bar{n}\in(\mathbb{Z}/p\mathbb{Z})^*\). Thus \(f\) is welldefined. 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 nonsquares to nonsquares. 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 2ik\mbox{ and }2^{m2}jl. \] 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 \(db\). 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 nonnegative 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 squarefree. 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^2sx^2\) and \(s\) is squarefree so \(rsx\). 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^24ac\pmod{4an}. \] Using the above method for square roots, we may determine whether \(b^24ac\) is a square in the integers modulo \(4an\) and, if so, we can take each integer \(y\) with \(y^2\equiv b^24ac\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{p1}{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\). 
20170225, 23:00  #2 
"Matthew Anderson"
Dec 2010
Oregon, USA
2×3×7×17 Posts 
Hi Mersenneforum,
In order to tackle this first number theory problem, (okay it is problem 84) I will try a similar problem. Find all x such that 5*x+6 is congruent to 0 mod 7 expression 1 From the reading, I notice that the greatest common divisor of 5 and 6 is 1. So the techniques presented here should apply. We make an augmented T table X 5*X 5*X mod 7 ______________________ 0 0 0 1 5 5 2 10 3 3 15 1 4 20 6 5 25 4 6 30 2 From expression 1, conclude that 5*x is congruent to 1 mod 7. My education has a gap here. I use my Maple computer tool to conclude that x is congruent to 2*x+1 mod 7. Here is my Maple code – a:=(5*x+6) mod 7 And, again, Maple returns a= 2*x+1 mod 7. Maybe someone can help me fill in the gaps. Regards, Matt 
20170225, 23:20  #3  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
but this equation isn't quadratic. edit: the solution like this for 84 is similar to this: Last fiddled with by science_man_88 on 20170225 at 23:41 

20170226, 10:09  #4  
Dec 2012
The Netherlands
5×331 Posts 
Quote:
An alternative approach is to multiply by 3 (because 3x5 mod 7=1): if \(5x+6\equiv 0\pmod{7}\) then \(3(5x+6)\equiv 0\pmod{7}\) and so \(x+4\equiv 0\pmod{7}\). I hope this helps! 

20170327, 06:01  #5 
"Matthew Anderson"
Dec 2010
Oregon, USA
2·3·7·17 Posts 
Hi Mersenneforum and Nick,
Thank you for the instruction about linear equations with a modulus. It helps. Regards, Matt 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 1 & 2  Nick  Number Theory Discussion Group  17  20171223 20:10 
Basic Number Theory 20: polynomials  Nick  Number Theory Discussion Group  5  20170425 14:32 
Basic Number Theory 17: quadratic reciprocity  Nick  Number Theory Discussion Group  0  20170131 14:41 
Basic Number Theory 14: a first look at groups  Nick  Number Theory Discussion Group  0  20161229 13:47 
Basic Number Theory 13: Pythagorean triples and a few Diophantine equations  Nick  Number Theory Discussion Group  2  20161218 14:49 