mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2017-02-22, 13:08   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2×751 Posts
Default 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\).
Nick is online now   Reply With Quote
Old 2017-02-25, 23:00   #2
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

11578 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Old 2017-02-25, 23:20   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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\\<br />
5x\equiv -6 \pmod 7 \\<br />
5\equiv -2 \pmod 7 \\ <br />
\therefore  \\<br />
5x\equiv -2x \pmod 7 \\<br />
-6 \equiv -2x\pmod 7 \\<br />
3 \equiv x \pmod 7  \\<br />

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} \\<br />
12x+24 \equiv 0 \pmod {33} \\<br />
3(4x+8)\equiv 0 \pmod {3(11)}\\<br />
(4x+8)\equiv 0 \pmod {11}\\<br />
4(x+2)\equiv 0 \pmod {11}\\<br />
\text { by 0 product rule one of these has to be 0 and 4 is not 0} \\<br />
x+2 \equiv 0 \pmod {11}\\<br />
x\equiv -2 \pmod {11}\\<br />
x \equiv 9 \pmod {11}\\<br />

Last fiddled with by science_man_88 on 2017-02-25 at 23:41
science_man_88 is offline   Reply With Quote
Old 2017-02-26, 10:09   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·751 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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!
Nick is online now   Reply With Quote
Old 2017-03-27, 06:01   #5
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

7×89 Posts
Default

Hi Mersenneforum and Nick,

Thank you for the instruction about linear equations with a modulus.
It helps.

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Basic Number Theory 20: polynomials Nick Number Theory Discussion Group 5 2017-04-25 14:32
Basic Number Theory 17: quadratic reciprocity Nick Number Theory Discussion Group 0 2017-01-31 14:41
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47
Basic Number Theory 13: Pythagorean triples and a few Diophantine equations Nick Number Theory Discussion Group 2 2016-12-18 14:49

All times are UTC. The time now is 17:46.

Sat Nov 28 17:46:08 UTC 2020 up 79 days, 14:57, 3 users, load averages: 1.43, 1.36, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.