mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-01-31, 14:41   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

101110111102 Posts
Default Basic Number Theory 17: quadratic reciprocity

Which numbers are squares?
More precisely, for which \(a\) does there exist \(x\) with \(x^2=a\)?
The answer depends on which number system we work in, of course.
In the real numbers, if \(a\geq 0\) then \(a\) is a square (put \(x=\sqrt{a}\)),
while if \(a<0\) then it is not a square (since \(x^2\geq 0\) for all real \(x\)),
so the squares are precisely the non-negative numbers.
It follows, for any real numbers \(x,y\), that if \(x\) is not a square and \(y\) is not a square
then their product \(xy\) is a square.
This is a pattern that we shall see again shortly.

Let \(n\) be a positive integer.
An integer \(a\) is called a quadratic residue modulo \(n\) if there exists an integer \(x\) such that \(x^2\equiv a\pmod{n}\)
(or, equivalently, if \(\bar{a}\) is a square in \(\mathbb{Z}/n\mathbb{Z}\)).
As ever in modular arithmetic, the key is to understand what happens modulo the prime numbers.
And every integer is a quadratic residue modulo 2, so we focus on odd primes.

Let \(p\) be an odd prime number.
For each integer \(a\), we define the Legendre symbol \((\frac{a}{p})\) as follows:
  • if \(p\) divides \(a\) then \((\frac{a}{p})=0\).
  • If \(p\) does not divide \(a\) then \((\frac{a}{p})=1\) if \(a\) is a quadratic residue modulo \(p\), and -1 otherwise.
For example, \((\frac{-15}{5})=0\), \((\frac{19}{5})=1\) and \((\frac{3}{5})=-1\).

Proposition 99
Let \(p\) be an odd prime number.
Then, for all integers \(a\),
\[ \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}. \]

proof
Take any integer \(a\).
If \(p|a\) then \((\frac{a}{p})=0\equiv a^{\frac{p-1}{2}}\pmod{p}\).
Suppose \(p\) does not divide \(a\).
Then (by corollary 40) \(a^{p-1}\equiv 1\pmod{p}\)
so (by proposition 60) \(a^{\frac{p-1}{2}}\equiv 1\pmod{p}\) or \(a^{\frac{p-1}{2}}\equiv -1\pmod{p}\).
Now the unit group of the integers modulo \(p\) is cyclic (by theorem 90)
so there exists an integer \(g\) such that
\[ \left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{1},\bar{g},\bar{g}^2,\bar{g}^3, \ldots,\bar{g}^{p-2}\} \]
with \(\bar{g}^{p-1}=\bar{1}\).
Let \(H=\{\bar{g}^{2n}:n\in\mathbb{Z}\}\), the set of all squares in \((\mathbb{Z}/p\mathbb{Z})^*\).
Then \(H\) is the cyclic subgroup generated by \(\bar{g}^2\) and, by proposition 86, \(H\) has precisely \(\frac{p-1}{2}\) elements, i.e.
\[ H=\{\bar{1},\bar{g}^2,\bar{g}^4,\bar{g}^6,\ldots,\bar{g}^{p-3}\}. \]
As \(p\) does not divide \(a\), \(\bar{a}\) is an element of \((\mathbb{Z}/p\mathbb{Z})^*\), so \(\bar{a}=\bar{g}^r\) for some \(r\in\{0,1,\ldots,p-2\}\).
If \((\frac{a}{p})=1\) then \(\bar{a}\in H\) so \(r\) is even, i.e. \(r=2s\) for some integer \(s\), and therefore \(\bar{a}^{\frac{p-1}{2}}=\bar{g}^{s(p-1)}=\bar{1}\) giving \(a^{\frac{p-1}{2}}\equiv 1\pmod{p}\).
Conversely, if \(a^{\frac{p-1}{2}}\equiv 1\pmod{p}\) then \(\bar{g}^{\frac{r(p-1)}{2}}=\bar{1}\) and \(\bar{g}\) has order \(p-1\) so, by proposition 75, \(p-1\) divides \(\frac{r(p-1)}{2}\).
Thus \(r\) is even and \(\bar{a}=\bar{g}^r\in H\), hence \((\frac{a}{p})=1\). ∎

Corollary 100
Let \(p\) be an odd prime number.
Then, for all integers \(a,b\), \((\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})\).

proof
For any integers \(a,b\), proposition 99 gives
\[ \left(\frac{ab}{p}\right)\equiv (ab)^{\frac{p-1}{2}}
=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv
\left(\frac{a}{p}\right) \left(\frac{b}{p}\right)\pmod{p} \]
hence \((\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})\). ∎

In particular, for any odd prime number \(p\) and integers \(a,b\),
if \(a\) is not a square modulo \(p\) and \(b\) is not a square modulo \(p\)
then their product \(ab\) is a square modulo \(p\) (just as with real numbers).

Recall that, for any integer \(a\) and positive integer \(n\), we write \(a\bmod{n}\) for the remainder on dividing \(a\) by \(n\),
which is an integer in the range 0 to \(n-1\) inclusive.

Proposition 101
Let \(p\) be an odd prime number and \(a\) an integer not divisible by \(p\).
Define \(A=\{a,2a,3a,\ldots,\frac{p-1}{2}a\}\) and \(r=\#\{x\in A:x\bmod{p}>\frac{p}{2}\}\).
Then \((\frac{a}{p})=(-1)^r\).

proof
Each element of the set \(A\) is congruent (modulo \(p\)) with a unique integer between \(-\frac{p}{2}\) and \(\frac{p}{2}\),
and no element of \(A\) is congruent with 0 (modulo \(p\)) so all these integers are positive or negative.
Let \(r_1,r_2,\ldots,r_k\) be the positive ones and \(-s_1,-s_2,\ldots,-s_m\) the negative ones.
(Thus \(k,m\) are non-negative integers with \(k+m=\frac{p-1}{2}\) and, for each \(i\in\{1,2,\ldots,k\}\) and each \(j\in\{1,2,\ldots,m\}\) we have \(0<r_i<\frac{p}{2}\) and \(0<s_j<\frac{p}{2}\).)
Moreover, for any \(x,y\in A\), if \(x\equiv y\pmod{p}\) or \(x\equiv -y\pmod{p}\) then \(x=y\) (since \(p\) does not divide \(a\) or any positive integer less than \(p\))
so \(r_1,r_2,\ldots,r_k,s_1,s_2,\ldots,s_m\) are all distinct, and \(r=m\).
But there are only \(\frac{p-1}{2}\) distinct integers greater than 0 and less than \(\frac{p}{2}\),
so the integers \(r_1,r_2,\ldots,r_k,s_1,s_2,\ldots,s_m\) are precisely the integers \(1,2,\ldots,\frac{p-1}{2}\) in some order,
and therefore
\[ a^{\frac{p-1}{2}}\left(\frac{p-1}{2}!\right)
=a(2a)(3a)\ldots \left(\frac{p-1}{2}a\right)
\equiv r_1r_2\ldots r_k(-s_1)(-s_2)\ldots (-s_m)
=(-1)^m\left(\frac{p-1}{2}!\right)\pmod{p}. \]
As \(p\) does not divide \(\frac{p-1}{2}!\), it follows that \(a^{\frac{p-1}{2}}\equiv (-1)^m\pmod{p}\)
hence, by proposition 99, \((\frac{a}{p})\equiv (-1)^m\pmod{p}\).
And \(r=m\) (with \(p>2\)) so \((\frac{a}{p})=(-1)^r\). ∎

Example
For which odd prime numbers \(p\) is 2 a square modulo \(p\)?
Let \(A=\{2,4,6,\ldots,p-1\}\).
In this case, all elements of \(A\) are less than \(p\), so we simply need to count how many of them are greater than \(\frac{p}{2}\).
If \(p\equiv 1\pmod{4}\) then the elements of \(A\) greater than \(\frac{p}{2}\) are \(\{\frac{p+3}{2},\frac{p+7}{2},\ldots,p-1\}\).
There are \(\frac{p-1}{4}\) elements here, so \((\frac{2}{p})=(-1)^{\frac{p-1}{4}}\) which is 1 if and only if \(p\equiv 1\pmod{8}\).
If instead \(p\equiv 3\pmod{4}\) then the elements of \(A\) greater than \(\frac{p}{2}\) are \(\{\frac{p+1}{2},\frac{p+5}{2},\ldots,p-1\}\).
There are \(\frac{p+1}{4}\) elements here, so \((\frac{2}{p})=(-1)^{\frac{p+1}{4}}\) which is 1 if and only if \(p\equiv -1\pmod{8}\).
Conclusion: for any odd prime number \(p\), 2 is a quadratic residue modulo \(p\) if and only if \(p\equiv\pm 1\pmod{8}\).

For distinct odd prime numbers \(p,q\), we can consider whether \(p\) is a quadratic residue modulo \(q\) and also whether \(q\) is a quadratic residue modulo \(p\) and, at first sight, there is no reason why these two questions should be related.
It is one of the gems of Number Theory that there is a simple relationship between them. Before we can prove this, we need a small lemma.

Lemma 102
Let \(p,q\) be odd positive integers, \(A=\{1,2,\ldots,\frac{p-1}{2}\}\), and \(B=\{1,2,\ldots,\frac{q-1}{2}\}\).
Define \(U=\{(a,b)\in A\times B:aq-bp<-\frac{p}{2}\}\) and \(W=\{(a,b)\in A\times B:aq-bp>\frac{q}{2}\}\).
Then \(\#U=\#W\).

proof
Let \(f:A\rightarrow A\) be the function \(a\mapsto \frac{p+1}{2}-a\)
and \(g:B\rightarrow B\) be the function \(b\mapsto \frac{q+1}{2}-b\).
Then \(f,g\) are each bijective with \(f^{-1}=f\) and \(g^{-1}=g\).
Take any \(a\in A\) and any \(b\in B\).
Then
\[ f(a)q-g(b)p
=\left(\frac{p+1}{2}-a\right)q-\left(\frac{q+1}{2}-b\right)p
=\frac{q}{2}-\frac{p}{2}-(aq-bp). \]
If \((a,b)\in U\) then \(aq-bp<-\frac{p}{2}\) so \(\frac{q}{2}-\frac{p}{2}-(aq-bp)>\frac{q}{2}\) and therefore \((f(a),g(b))\in W\).
Conversely, if \((a,b)\in W\) then \(aq-bp>\frac{q}{2}\) so \(\frac{q}{2}-\frac{p}{2}-(aq-bp)<-\frac{p}{2}\) and therefore \((f^{-1}(a),g^{-1}(b))=(f(a),g(b))\in U\).
Hence the function \(h:U\rightarrow W\) given by \((a,b)\mapsto (f(a),g(b))\) is bijective and it follows that \(\#U=\#W\). ∎

Theorem 103
Let \(p,q\) be distinct odd prime numbers. Then
\[ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right)
=\left(-1\right)^{\frac{(p-1)(q-1)}{4}}. \]

proof
Let \(A=\{1,2,\ldots,\frac{p-1}{2}\}\) and \(B=\{1,2,\ldots,\frac{q-1}{2}\}\).
For each \(a\in A\), there exist unique integers \(b,r\) such that \(aq=bp+r\) and \(0\leq r<p\) (by propostion 5).
Let \(s\) be the number of \(a\in A\) for which we get \(r>\frac{p}{2}\).
Then \((\frac{q}{p})=(-1)^s\) by proposition 101.
Instead of taking the remainder \(r\) in the range 0 to \(p-1\) inclusive, we may take it in the range \(-\frac{p-1}{2}\) to \(\frac{p-1}{2}\) inclusive,
and then \(s\) is the number of \(a\in A\) for which we get \(r<0\).
As the quotient \(b\) is unique in each case, we also have \(s=\#S\)
where \(S=\{(a,b)\in\mathbb{Z}^2:a\in A,-\frac{p}{2}<aq-bp<0\}\).
Take any \((a,b)\in S\).
Then \(bp>aq\) with \(p,a,q\) all positive so \(b>0\) (and \(b\) is an integer) hence \(b\geq 1\).
Also \(bp<aq+\frac{p}{2}\) and \(a<\frac{p}{2}\) so \(b<\frac{q+1}{2}\) (and \(b\) is an integer) hence \(b\leq\frac{q-1}{2}\).
Thus \(b\in B\) and
\[ S=\{(a,b)\in A\times B:-\frac{p}{2}<aq-bp<0\}. \]
In exactly the same way (swapping \(p\) with \(q\), \(a\) with \(b\) but also the order of the coordinates), if we let \(T=\{(a,b)\in A\times B:0<aq-bp<\frac{q}{2}\}\) and \(t=\#T\) then \((\frac{p}{q})=(-1)^t\).
Define
\[\begin{eqnarray*}
U & = & \left\{(a,b)\in A\times B:aq-bp<-\frac{p}{2}\right\} \\
V & = & \left\{(a,b)\in A\times B:-\frac{p}{2}<aq-bp<\frac{q}{2}\right\} \\
W & = & \left\{(a,b)\in A\times B:aq-bp>\frac{q}{2}\right\}
\end{eqnarray*}\]
Then the sets \(U,V,W\) form a partition of \(A\times B\) so \(\#(A\times B)=\#U+\#V+\#W\).
For any \(a\in A\) and any \(b\in B\), \(p\) does not divide \(a\) and the primes \(p,q\) are distinct so \(aq-bp\neq 0\).
Thus \(\#V=\#S+\#T=s+t\).
And by lemma 102 we have \(\#U=\#W\) so
\[ s+t=\#V\equiv\#(A\times B)=\frac{p-1}{2}\cdot\frac{q-1}{2}\pmod{2} \]
hence \(\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)=(-1)^{s+t}=\left(-1\right)^{\frac{(p-1)(q-1)}{4}}\). ∎

Corollary 104 Quadratic Reciprocity
Let \(p,q\) be distinct odd prime numbers.
If \(p\equiv 1\pmod{4}\) or \(q\equiv 1\pmod{4}\) (or both)
then \((\frac{q}{p})=(\frac{p}{q})\), and otherwise \((\frac{q}{p})=-(\frac{p}{q})\).

proof
If \(p\equiv 1\pmod{4}\) or \(q\equiv 1\pmod{4}\) then \(\frac{(p-1)(q-1)}{4}\) is even so, by theorem 103, \((\frac{p}{q})(\frac{q}{p})=1\) and therefore \((\frac{q}{p})=(\frac{p}{q})\).
If instead \(p\equiv q\equiv 3\pmod{4}\) then \(\frac{(p-1)(q-1)}{4}\) is odd so, by theorem 103, \((\frac{p}{q})(\frac{q}{p})=-1\) and therefore \((\frac{q}{p})=-(\frac{p}{q})\). ∎

Example
Is 87 a square modulo 127?
Using corollary 100 and corollary 104, we see that
\[\begin{eqnarray*}
\left(\frac{87}{127}\right)
& = & \left(\frac{3}{127}\right) \left(\frac{29}{127}\right)
= -\left(\frac{127}{3}\right) \left(\frac{29}{127}\right) \\
& = & -\left(\frac{1}{3}\right) \left(\frac{29}{127}\right)
= -\left(\frac{29}{127}\right)
= -\left(\frac{127}{29}\right) \\
& = & -\left(\frac{11}{29}\right)
= -\left(\frac{29}{11}\right)
= -\left(\frac{7}{11}\right) \\
& = & \left(\frac{11}{7}\right)
= \left(\frac{4}{7}\right)=1
\end{eqnarray*}\]
so 87 is a square modulo 127.


Exercises
79. Is 65 a quadratic residue modulo 31?
80. For which odd prime numbers \(p\) is -2 a square modulo \(p\)?
81. Find all integers \(x\) such that \(x^2\equiv 1\pmod{12}\).
82. Let \(z\) be a complex number such that \(z^8=1\) but \(z^4\neq 1\). Show that \(z+z^{-1}=\pm\sqrt{2}\).

Last fiddled with by Nick on 2017-08-18 at 17:17 Reason: Typo (found by wreck - thank you!)
Nick 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 18: quadratic equations modulo n Nick Number Theory Discussion Group 4 2017-03-27 06:01
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47
Basic Number Theory 3: gcd, lcm & Euclid's algorithm Nick Number Theory Discussion Group 5 2016-10-08 09:05

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

Sat Nov 28 17:54:25 UTC 2020 up 79 days, 15:05, 3 users, load averages: 1.09, 1.10, 1.25

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.