MAT 338 Day 27 2011

2427 days ago by kcrisman

The whole point of the end of last time was to convince you of two things regarding quadratic congruences:
  1. You really only need to worry about prime moduli because of the Chinese Remainder Theorem and Hensel's Lemma.  (I added a minor point in Hensel's Lemma to last time's notes to make sure it dealt with everything - a technical condition that will usually be true.)
  2. You really only need to worry about solving $x^2\equiv a\text{ mod }(p)$ because more complicated quadratic congruences can be reduced to this by completing the square or related procedures.
So we will talk solely about finding square roots mod ($p$) for the next week solid.

 

However, it is not so easy to just find square roots - or even when there is a square root - modulo $p$ in general.  To get a flavor for this, our final goal for today is to explore for which $p$ it is true that $x^2\equiv 2$ mod ($p$) has a solution.  Or, to put it another way, when does two have a square root modulo $p$?  First do some by hand; for what primes up to 20 does $2$ have a square root? Then we'll look at more data below.

@interact def _(odd_primes_up_to=50): for p in prime_range(3,odd_primes_up_to): solutions=solve_mod([x^2==2],p) if len(solutions)!=0: html("$x^2\equiv 2\\text{ mod }(%s)$ has solutions $%s$ and $%s$"%(p,solutions[0][0],solutions[1][0])) else: html("No solutions modulo $%s$"%p) 
       

Click to the left again to hide and once more to show the dynamic interactive window

What do you think?  Any patterns?

 

As it turns out, it is quite hard to prove such patterns without the benefit of powerful theoretical machinery.  Which means it is hard to even know whether there is a solution to a given congruence without such machinery!  That is what the next week will be about.

In fact, it is even hard to conjecture such things for harder cases unless you are quite clever. Euler was one of the first to do so. Here are three links for a very unusual paper of Euler's - one where he included nary a proof, just closely related conjectures to this question!

Next, I have a handout of more tables made by the great Italian-French mathematician Lagrange. Lagrange gave proofs of many of the patterns in quadratic forms (what numbers look like $a^2+b^2$, $a^2+2b^2$, etc.) that Fermat and Euler talked about.   We already know two of his theorems; if you ever read any science fiction or space stuff that talks about stable places to orbit being called Lagrange points - that's him too. Lagrange was Euler's successor in Berlin after he went back to Russia under the stable (if despotic) regime of Catherine the Great; later he moved to France and was quite influential there.

 But what made things work out best was a couple innovations of Lagrange's successor, Adrien-Marie Legendre - innovations Gauss made great use of. We now introduce two definitions, a little more formal in nature. Both assume that $a\not\equiv 0$ mod ($p$):
  1. If there is a solution of $x^2\equiv a$ mod ($p$) we say that $a$ is a quadratic residue of $p$ (or a QR).
  2. If there is not a solution of $x^2\equiv a$ mod ($p$) we say that $a$ is a quadratic nonresidue of $p$.
Note that this is the same thing as saying that $a$ does or does not have a square root modulo $p$, but the focus changes to $a$ instead of the square root itself.  The terminology is explained by the fact that the equivalence classes $[a]$ are called residues (we did that too earlier), so one which is a square is quadratic.  Sage can calculate these for us, of course.
quadratic_residues(17) 
       
[0, 1, 2, 4, 8, 9, 13, 15, 16]
[0, 1, 2, 4, 8, 9, 13, 15, 16]
least_quadratic_nonresidue(17) 
       
3
3

Note this last function gives the smallest nonresidue, in case you need it. 

One can approach this subject from many vantage points.  However, we have the advantage of having developed the basics of groups and primitive roots, which will simplify much of our exposition.  

Group theory approach to quadratic residues:

  • Consider the set of all (again, non-zero) quadratic residues modulo some $p$.
    • Call it $Q_p$ (by analogy with $\mathbb{Z}_p$ and $U_p$).  
  • It is clear that $1\in Q_p$, since $1\equiv 1^2$.  
  • Additionally, if $a$ and $b$ are both in $Q_p$ (with $a\equiv s^2$ and $b\equiv t^2$), 
    • then $ab$ is also a quadratic residue (since $(st)^2\equiv s^2 t^2\equiv ab$).  
  • So $Q_p$ is already almost a group all by itself, since multiplication works and $1$ is in it.  
  • Since it is a subset of $U_p$, we would call it a subgroup.

In fact, $Q_p$ is a group!  

  • Assume that $a\equiv s^2\in Q_p$.  
  • Then note that $$\left(s^{-1}\right)^2 a\equiv \left(s^{-1}\right)^2 s^2\equiv \left(s\cdot s^{-1}\right)^2\equiv 1$$ 
  • So by definition $$\left(s^{-1}\right)^2=a^{-1}\; ,$$ which means that if $a\in Q_p$ then $a^{-1}\in Q_p$ as well.
  • So $Q_p$ is closed under inverses, making it a group.  (For those more interested in this, $Q_p$ is in fact a quotient group of $U_p$ - see page 122 in Jones and Jones.)

You might be wondering how this piece of $U_p$ connects to the most important thing we've seen so far about $U_p$.  Recall that $U_p$ was cyclic, that it had a generator whose powers gave us all units modulo $p$.  We called such an element a primitive root of $p$.

g=mod(primitive_root(19),19);g 
       
2
2

So let's compare the primitive root's powers and the quadratic residues.  Shouldn't be too hard...

L=[g^n for n in range(1,19)] L;quadratic_residues(19) 
       
[2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1]
[0, 1, 4, 5, 6, 7, 9, 11, 16, 17]
[2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1]
[0, 1, 4, 5, 6, 7, 9, 11, 16, 17]

This exemplifies a major fact.

Fact: For odd prime modulus $p$, the quadratic residues are precisely the even powers of a primitive root $g$.  

  • Certainly $g^{2n}=\left(g^n\right)^2$, so the even powers of $g$ are QR.  
  • But also note that if $a\in Q_p$ and $a=s^2$, that $s$ and $a$ are themselves still powers of $g$ (by definition of $g$).  
  • So if $s=g^n$ and $a=g^m$ for some $n,m$, then $$a=g^m\equiv g^{2n}\text{ mod }(p)\; ;$$ so $$m\equiv 2n\text{ mod }(p-1)\; .$$
  • This is only possible if $m$ is even since $p-1$ and $2n$ are even.

This will turn out to be a fantastically useful theoretical way to find $Q_p$.  It will show up in lots of proofy settings.

 

However, this is a terrible way to actually find quadratic residues for a given $p$, since it involves finding a primitive root and listing lots of powers!  We need both theory and practice.

Here is a much easier way.  Recall our observation about the middle column in the colorful matrix of powers modulo a prime: $$a^{(p-1)/2}\equiv\pm 1\text{ for all }a\text{ not divisible by }p\; .$$  The following extension of this is usually called Euler's Criterion.

Theorem:  If $p$ is an odd prime, then for all integers $a$ not a multiple of $p$ the sign of the following determines whether $a$ is a QR; $$a^{(p-1)/2}\equiv\pm 1\text{ mod }(p)\, ,$$ with $+1$ if $a$ is a QR, otherwise $-1$.

Proof:

  • Let $g$ be a primitive root of $p$, so that $a\equiv g^i$ for some $i$.  
  • Then if we let $h=g^{(p-1)/2}$, Fermat's Little Theorem shows that $$h^2=g^{p-1}\equiv 1\text{ mod }(p)\, .$$ 
  • Since $g$ is primitive, $h\equiv 1$ is impossible, so $h\equiv -1$.  
  • But then $$a^{(p-1)/2}\equiv \left(g^i\right)^{(p-1)/2}\equiv \left(g^{(p-1)/2}\right)^i\equiv h^i \equiv (-1)^i\, .$$ 
  • This is $+1$ when $i$ is even and $-1$ when $i$ is odd - which is precisely when $a$ is a quadratic residue and nonresidue, respectively.

Example:

Notice that this immediately gives our old result that $-1$ has a square root modulo an odd prime $p$ precisely when $p\equiv 1$ mod (4), because $(-1)^{(p-1)/2}=+1$ precisely when $(p-1)/2$ is even, or $p\equiv 1$ mod (4).  That is MUCH easier than our previous ad-hoc way of doing it!

Using this same idea, we can prove a very nice result about when a composite number is a QR.

Proposition: If $n=ab$ is a factorization (not necessarily nontrivial) of $n$, then $n$ is a QR of $p$ precisely when either both $a$ and $b$ are QRs of $p$ or both $a$ and $b$ are not QRs of $p$.  (Hence if one of $a,b$ is and the other isn't, neither is $n$.)

Proof: Modulo $p$, write $a\equiv g^i$ and $b\equiv g^j$ for some $i,j$.  Then $n=ab\equiv g^{i+j}$, and $i+j$ is even when $i$ and $j$ have the same parity.  Because of our fact about even powers of the primitive root, this is exactly the same thing as the conclusion of the proposition.

Now I can immediately decide that $-2\equiv 21$ is not a QR mod (23) by the fact that $-1$ is not a QR but 2 is, which we knew before.  Likewise, I can immediately decide that $-2\equiv 9$ is a QR mod (11) by the fact that neither $-1$ nor $2$ is a QR.

quadratic_residues(23) 
       
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
quadratic_residues(11) 
       
[0, 1, 3, 4, 5, 9]
[0, 1, 3, 4, 5, 9]

Now there is a very convenient way to notate all this, devised by Legendre, which takes advantage of the fact that $a=g^i$ is an even power exactly when $a$ is a QR, and $(-1)^i=1$ precisely when $i$ is even (and hence precisely when $a$ is a QR).  This is the so-called Legendre symbol.  The command in Sage is pretty straightforward.

legendre_symbol(-2,11) 
       
1
1
@interact def _(p=(17,prime_range(50))): for n in [q for q in quadratic_residues(p) if q!=0]: html("$%s$ is a QR of $%s$ and $\left(\\frac{%s}{%s}\\right)=%s$"%(n,p,n,p,legendre_symbol(n,p))) 
       

Click to the left again to hide and once more to show the dynamic interactive window

We write $\left(\frac{a}{p}\right)$ for the Legendre symbol, so e.g. $\left(\frac{-1}{p}\right)=1$ for $p$ prime if and only if $p=2$ or $p\equiv 1$ mod (4).

We define the Legendre symbol of $a$ modulo $p$ to be zero if $p\mid a$.  

  • On the one hand, this recognizes the special case that $0^2=0$, while $1=1^2=(-1)^2$ (and everything else) usually have two square roots modulo a prime.  
  • On the other hand, this also conveniently ignores the only integer from $0$ to $p-1$ which is not in $U_p$, so that in fact you can think of $x\to \left(\frac{x}{p}\right)$ to be a function from $U_p$ to $\{1,-1\}$ of the kind we call a group homomorphism.  (Indeed, it gets us from a cyclic group of order $p-1$ to a cyclic group of order $2$, with "kernel" a cyclic group of order $(p-1)/2$.)

Let's use our usual example to visualize the tension and connection between primitive roots and quadratic residues.  

Question: Before looking at it, do you see why a quadratic residue automatically can't be a primitive root?

@interact def _(p=(13,prime_range(50))): P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]),cmap='jet') show(P) 
       

Click to the left again to hide and once more to show the dynamic interactive window

Here is another way to view the tension between primitive roots and quadratic residues (which automatically can't be primitive roots; do you see why?).  All the residues are the second column (correctly labeled 1), and all the quadratic residues are the colors in the third column (labeled 2 as they are squares).  See how that column is symmetric about the middle of the rows, with two of each of the colors appearing.  Note that these are the same colors as every other column in a row with a primitive root (the rows with every color represented), though not necessarily in that order.  Also notice that the color of the middle column determines whether the color beginning that row shows up in the second column.  Weird!  Yet true.

 

Here's a final fun thing.  What is the sum of all Legendre symbols for a given prime?

@interact def _(p=(19,prime_range(100))): L = [legendre_symbol(a,p) for a in [0..p-1]] html("All Legendre symbols $\left(\\frac{a}{%s}\\right)$ can be listed:"%p) print L html("And they sum up to $%s$"%sum(L)) 
       

Click to the left again to hide and once more to show the dynamic interactive window

This is cool, and a nice example of the kind of fun one can have experimenting.  What do you think?  Do you think we can prove it?

 

 
       

Homework, due Monday:

  1. Show that $x^3=y^2-999$ has no integer solutions.
  2. Show that the Pell equation $x^2-dy^2=1$, where $d$ is a perfect square, has just two solutions.
  3. Look up the current best known bound on the number of integer points on a Mordell equation curve.
  4. Verify that if $$x_0^2-ny_0^2=k\text{ and }x_1^2-ny_1^2=\ell$$ then $$x=x_0x_1+ny_0y_1,\; y=x_0y_1+y_0x_1\text{ solves }x^2-ny^2=k\ell\; .$$
  5. Explain why the previous problem reduces to the method we used in the examples if we are trying to find use a tangent line to find more integer solutions to $x^2-5y^2=1$.
  6. Find a non-trivial integer solution to $x^2-17y^2=-1$, and use it to get a nontrivial solution to $x^2-17y^2=1$.
  7. Recreate the above geometric construction using tangent lines on the hyperbola with $x^2-5y^2=1$, and use it find three (positive) integer points on this curve with at least two digits for both $x$ and $y$.  Yes, you will have to find a non-trivial solution on your own; it's not hard, there is one with single digits.
  8. Prove that if $e>1$, then there is no solution to $$x^2\equiv -1\text{ mod }(2^e)\; ;$$ use our knowledge of squares modulo 4.
  9. For what $n$ does $-1$ have a square root modulo $n$?  (Hint: prime factorization and the previous problem.)
  10. Solve $x^2+3x+5\text{ mod }(15)$ using completion of squares and trial and error for square roots to confirm the computation above.
  11. Solve the following congruences without using a computer:
    • $x^2+6x+5$ mod (17)
    • $5x^2+3x+1$ mod (17)
  12. Prove that $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .$$
  13. Show that a quadratic residue can't be a primitive root if $p>2$.
  14. Use Euler's Criterion to find all quadratic residues of 13.
  15. Use Euler's Criterion to prove that $2$ has a square root modulo $p$ if $p\equiv 1\text{ mod }(8)$.  (We'll prove the rest of your conjecture next time.)