mersenneforum.org > Math Basic Number Theory 18: quadratic equations modulo n
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-02-22, 13:08 #1 Nick     Dec 2012 The Netherlands 3·541 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$$.
 2017-02-25, 23:00 #2 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 22·167 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
2017-02-25, 23:20   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by MattcAnderson 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
$5x+6 \equiv 0 \pmod 7\\
5x\equiv -6 \pmod 7 \\
5\equiv -2 \pmod 7 \\
\therefore \\
5x\equiv -2x \pmod 7 \\
-6 \equiv -2x\pmod 7 \\
3 \equiv x \pmod 7 \\
$

but this equation isn't quadratic.

edit:

the solution like this for 84 is similar to this:

$\text {deleted previous ramble after checking with PARI/GP} \\
12x+24 \equiv 0 \pmod {33} \\
3(4x+8)\equiv 0 \pmod {3(11)}\\
(4x+8)\equiv 0 \pmod {11}\\
4(x+2)\equiv 0 \pmod {11}\\
\text { by 0 product rule one of these has to be 0 and 4 is not 0} \\
x+2 \equiv 0 \pmod {11}\\
x\equiv -2 \pmod {11}\\
x \equiv 9 \pmod {11}\\
$

Last fiddled with by science_man_88 on 2017-02-25 at 23:41

2017-02-26, 10:09   #4
Nick

Dec 2012
The Netherlands

31278 Posts

Quote:
 Originally Posted by MattcAnderson 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.
Yes, and only one row in your table has 5x mod 7 = 1...

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!

 2017-03-27, 06:01 #5 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 22×167 Posts Hi Mersenneforum and Nick, Thank you for the instruction about linear equations with a modulus. It helps. Regards, Matt

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2017-01-31 14:41 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 2 2016-12-18 14:49

All times are UTC. The time now is 22:35.

Thu Mar 4 22:35:13 UTC 2021 up 91 days, 18:46, 0 users, load averages: 2.31, 1.61, 1.52