# MAT 338 Day 26 2011

## 2946 days ago by kcrisman

Recall that last time we saw that if we

• connect two integer points on some conics (or look at the tangent to an integer point),
• then move a line with the same slope to a predefined reference point (like the origin),

we will always get a rational point, and often an integer point!

var('x,y') f(x)=(1/2)*x^2 viewsize=10 @interact def _(point1=(4,[-10,-8..10]),point2=(2,[-10,-8..10])): plot1 = plot(f,-viewsize,viewsize) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [0..viewsize^2]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if f(coords[0])==coords[1]] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) if point1 != point2: line1 = plot((f(point1)-f(point2))/(point1-point2)*(x-point1)+f(point1),-viewsize,viewsize,color='red') line2 = plot((f(point1)-f(point2))/(point1-point2)*x,-viewsize,viewsize,color='red',linestyle='--') show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2,ymin=-1,ymax=viewsize^2/2) else: line1 = plot(diff(f,x)(x=point1)*(x-point1)+f(point1),-viewsize,viewsize,color='red') line2 = plot(diff(f,x)(x=point1)*x,-viewsize,viewsize,color='red',linestyle='--') show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2,ymin=-1,ymax=viewsize^2/2)

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

Of course, we didn't need this to solve the case of the parabola; we could just use divisibility criteria!

But we will definitely want to use these ideas to study so-called Pell equations like $$x^2-2y^2=1$$  These were already rigorously discussed by Brahmagupta, as I mentioned before - clearly a quite old idea!

For instance, $x^2-2y^2=1$ was studied by Greeks such as Theon of Smyrna to shed light on $\sqrt{2}$.  What would this do?  Well, imagine that $(x,y)$ fulfill this.  Then divide and rearrange the original equation to get $$\frac{x^2}{y^2}=2+\frac{1}{y^2}$$ so that if you can find a solution to this equation with a big $y$, then $\frac{x^2}{y^2}$ is pretty close to $2$, which means $x/y$ is pretty close to $\sqrt{2}$.

Try to find some integer points on this curve.

var('x,y') @interact def _(viewsize=slider(10,20,1),d=2): f(x,y)=x^2-d*y^2 plot1 = implicit_plot(f-1,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 200) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[0]^2-d*coords[1]^2==1)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1)

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

Well, $\frac{3}{2}=1.5$ isn't too far from $\sqrt{2}\approx 1.414$, and $17/12\approx 1.417$ is even better.  Those Greeks!

Anyway, now that we have the idea of a potential way to get more integer points, let's try to use it on the hyperbola.  This would give new number theoretic solutions to $x^2-2y^2=1$, as well as (along the way) approximations to the square root of $2$.

• Algebraically, if $x^2-2y^2=1$, then the tangent line at any point $(x_0,y_0)$ is given by implicit differentiation to be $y'=\frac{x_0}{2y_0}$.
• What is the line through $(1,0)$ with that slope?  It's $y=\frac{x_0}{2y_0}(x-1)$, of course.
• So let's check where else this intersects the hyperbola, if at all.
• We start off with  $$x^2-2y^2-1=x^2-2\left(\frac{x_0}{2y_0}(x-1)\right)^2-1=$$ $$\left(1-\frac{x_0^2}{2y_0^2}\right)x^2+\left(\frac{x_0^2}{y_0^2}\right)x+\left(-1-\left(\frac{x_0^2}{2y_0^2}\right)\right)=0\, .$$
• This can be simplified to $$(2y_0^2-x_0^2)x^2+2x_0^2 x+(-2y_0^2-x_0^2)=0$$
• This, unbelievably, gives us (via the quadratic formula or factoring out $x-1$) $$x=\frac{-2x_0^2-4y_0^2}{-2x_0^2+4y_0^2}=\frac{x_0^2+2y_0^2}{x_0^2-2y_0^2}=x_0^2+2y_0^2$$
• So with a slick substitution of the original point, $$y=\frac{x_0}{2y_0}(x-1)=\frac{x_0}{2y_0}(x_0^2+2y_0^2-(x_0^2-2y_0^2))=2x_0 y_0\, .$$

Now let's try this with actual points!

@interact def _(x_0=17,y_0=12): x_1=x_0^2+2*y_0^2 y_1=2*x_0*y_0 html("Initial point was $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1)) html("And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_1,y_1,x_1^2-2*y_1^2))

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

d=2 var('x,y') @interact def _(x_0=3,y_0=2,lattice=False,auto_update=False): g(x,y)=x^2-d*y^2 x_1,y_1=x_0^2+2*y_0^2,2*x_0*y_0 plot1 = implicit_plot(g-1,(x_0-4,x_1+4),(x_0-4,x_1+4),plot_points = 200) grid_pts = [[i,j] for i in [x_0-4..x_1+4] for j in [x_0-4..x_1+4]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[0]^2-d*coords[1]^2==1)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) line1 = plot((x_0/(2*y_0))*(x-x_0)+y_0,x_0-4,x_1+4,color='red') line2 = plot((x_0/(2*y_0))*(x-1),x_0-4,x_1+4,color='red',linestyle='--') if lattice: show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2, figsize = [5,5], xmin = x_0-4, xmax = x_1+4, ymin = y_0-4, ymax = y_1+4, aspect_ratio=1) else: show(plot1+plot_lattice_pts+line1+line2, figsize = [5,5], xmin = x_0-4, xmax = x_1+4, ymin = y_0-4, ymax = y_1+4, aspect_ratio=1) html("The new points are $x_1=%s$ and $y_1=%s$"%(x_1,y_1))

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

Brahmagupta knew how to do this, though of course he did it both without our geometric interpretation (which was only made possible by Descartes and Fermat's introduction of coordinate systems) and also without the benefit of symbolically representing $\sqrt{2}$, which provides this alternate description of our thing above:

If $(x_0,y_0)$ is a solution to $x^2-2y^2=1$, then so is $(x_1,y_1)$ where $$(x_0+\sqrt{2}y_0)^2=x_1+\sqrt{2}y_1\, .$$

If you were to do the algebra out here, you'd get exactly the same answer as we did above.

Notice that once again we seem to have created a new number system, though this time with a square root of a positive, not negative number!  (And yes, it turns out that finding solutions to things like this is related to $\mathbb{Z}[\sqrt{2}]\cdots$ but we really won't pursue it further this time!

This does precisely corresponds to multiplying a group element by 2, e.g. $$[5]+ [5]\equiv 3\text{ mod }(7)\text{ is the same type of thing as }(3,2)+(3,2)=(17,12)\; .$$  And it turns out that there is a more general formula that corresponds to taking the line through two points and then moving it so that it goes through the original point $(1,0)$:

If $(x_1,y_1)$ and $(x_2,y_2)$ are both solutions of $x^2-2y^2=1$, then so is $$(x_1 x_2+2y_1 y_2, x_1 y_2+y_1 x_2)\,$$  If you apply this to two points opposite each other like $(3,2)$ and $(3,-2)$, you will get $$(3\cdot 3+2\cdot 2\cdot (-2),3\cdot (-2)+3\cdot 2)=(1,0)\, ,$$ which is then the group identity.

@interact(layout=[['x_0','y_0'],['x_1','y_1'],['auto_update']]) def _(x_0=3,y_0=2,x_1=17,y_1=12,auto_update=False): if x_0 != x_1: x_3,y_3=x_1*x_0+2*y_1*y_0,x_1*y_0+y_1*x_0 html("Initial points were $(%s,%s)$ and $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1,x_3,y_3)) html("And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_3,y_3,x_3^2-2*y_3^2)) elif y_0==y_1: x_3,y_3=x_0^2+2*y_0^2,2*x_0*y_0 html("Initial points were $(%s,%s)$ and $(%s,%s)$; new point is $(%s,%s)$."%(x_0,y_0,x_1,y_1,x_3,y_3)) html("And indeed $%s^2-2\cdot%s^2$ equals $%s$"%(x_3,y_3,x_3^2-2*y_3^2)) else: print "Input correct numbers!"

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

This ends up working for any $n$.  Just change all the "2"s above to "n".  Let's see this 'by hand' for $n=3$, where we solve $x^2-3y^2=1$ with $$2^2-3\cdot 1^2=1\; .$$

That is, I use $$x'=x^2+3y^2\text{ and }y'=2xy$$

x,y=2,1 x,y=x*x+3*y*y,x*y+y*x html("$%s^2-3\cdot%s^2=%s$"%(x,y,x^2-3*y^2))
 7^2-3\cdot4^2=1 7^2-3\cdot4^2=1

The general solution, given two points $(x_1,y_1)$ and $(x_2,y_2)$, would be, for $n>0$ and not a perfect square, $$x'=x_1x_2+ny_1y_2\text{ and }y'=x_1y_2+x_2y_1\; .$$

The same formula works for combining solutions of two different equations like the Pell.  $$\text{If }x_0^2-ny_0^2=k\text{ and }x_1^2-ny_1^2=\ell$$ $$\text{then }x=x_0x_1+ny_0y_1,\; y=x_0y_1+y_0x_1\text{ solves }x^2-ny^2=k\ell\; .$$  This is particularly nice if $k=\ell=-1$, because it would then give a solution to the Pell equation!

Brahmagupta used this (and more sophisticated things) to solve very hard ones, as did the later English mathematicians who answered a challenge of Fermat:

• Find a nontrivial solution to $x^2-61y^2=1$.
• Find a nontrivial solution to $x^2-109y^2=1$.

The smallest solution to the second one is $$x=158070671986249,y=15140424455100\; ,$$ which we can check below.  Considering that Brahmagupta says that finding the solution $x=1151,y=120$ to the equation $x^2-92y^2=1$ within a year proved the person "was a mathematician", we can be very thankful for computers!

158070671986249^2-109*15140424455100^2
 1 1

We have been doing a lot of stuff now with squares.  It is time to see one of the great theorems of numbers, which gives us great insight into the nature of squares in the integer world - and whose easiest proof involves lattice points!

What we will spend the next week doing is trying to find the solution a general problem, which I like to think of as the last piece of translating high school algebra to the modular world.  It is the task of solving $$x^2\equiv n\text{ mod }(p)\, ,$$ or finding square roots modulo $p$ a prime.  We have already done some of this, indeed!

Fact: $x^2\equiv 1$ mod ($p$) always has two solutions, $x\equiv \pm 1$.  So $1$ has two square roots modulo $p$.

Fact: $x^2\equiv -1$ mod ($p$) does not always have solutions.  It does when $p=2$ or when $p\equiv 1$ mod (4), and when it does there are two solutions, namely $$x\equiv \pm \left(\frac{p-1}{2}\right)!\, ,$$ as we finally proved a few days ago.

An interesting question that we really already know the answer to is when $-1$ has a square root for non-prime moduli.  We can ask Sage about this:

var('x') @interact def _(n=50): for i in [2..n]: sols = [sol[0] for sol in solve_mod([x^2==-1],i)] l = len(sols) if l!=0: html("$x^2=-1\\text{ mod }(%s)$ has $%s$ solutions, $%s$"%(i,l,sols))

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

Remember, we can get a total answer to this with Hensel's Lemma and the Chinese Remainder Theorem now.

• If we can solve, for a given prime $p$, $$f(x)\equiv0\text{ mod }(p)\; ,$$ then we can solve $$f(x)\equiv0\text{ mod }(p^e)\; .$$  (There is a technical condition that $p\nmid f'(x_0)$ for any original solution $x_0$.)
• If we can solve, for coprime integers $p$ and $q$, $$f(x)\equiv0\text{ mod }(p)\text{ and }(q)\; , then we can solve$$f(x)\equiv0\text{ mod }(pq)\; .$$Example: For instance, in going from p to p^2, we recall Day 10. Here, f(x)=x^2+1 is what we want a solution for. If we are looking mod (25), then we already know that mod (5) we have x\equiv 2 as a solution. Then a solution mod (25) (see notes from that day) will look like 2+k(5), and, remembering that f'(x)=2x, in fact it will satisfy$$\frac{2^2+1}{5}+k(2\cdot 2)\equiv 0\text{ mod }(5)$$which is 1+4k\equiv 0, which has solution k\equiv 1; hence a solution mod (25) should be 2+1(5)\equiv 7, and the computations above verify this! (Notice that 5\nmid f'(2)=4, so the technical condition is granted; otherwise we'd have to solve 1\equiv 0!) Example: Similarly, if I want solutions to x^2\equiv -1 mod (14) I should immediately note that although x^2\equiv -1 mod (2) has a solution, x^2\equiv -1 mod (7) does not (it's a prime of the form 4k+3) so I can't use the CRT. Example: But if I am looking mod (65), since 65=5\cdot 13 and x^2\equiv -1 has solutions both mod (5) and mod (13), I can use the CRT to combine them: • x\equiv 2 mod (5) • x\equiv 5 mod (13) • x\equiv 2\cdot 13\cdot (13^{-1}\text{ mod }(5))+5\cdot 5\cdot (5^{-1}\text{ mod }(13))\equiv 26\cdot 2+25\cdot 8\equiv 252\equiv 57\text{ mod }(65) And that also is consistent with the computations above! So all I care about, as far as just determining whether a solution exists, is prime moduli. Everything else is taken care of. Why we only care about square roots Now, it's not like x^2+k is the only game in town. What about other quadratics? It turns out that we can use something you are already familiar with to reduce the whole game to the following question: For what primes p is there a solution to x^2\equiv k\text{ mod }(p)? That is what we'll focus on for the next week or so. But let's look back at a general quadratic congruence. The Sage function "solve_mod" works, if a little naively. solve_mod([x^2-2*x+3==0],9)  [(5,), (6,)] [(5,), (6,)] This shows that x^2-2x+3\equiv 0 mod (9) has two solutions. How might I solve a general quadratic congruence? Example: The key is completing the square!$$x^2-2x+3=\left(x^2-2x+\left(\frac{2}{2}\right)^2\right)+3-\left(\frac{2}{2}\right)^2=(x-1)^2+2\, ,$$so$$(x-1)^2\equiv -2\text{ mod }(n)$$is the general congruence I want to solve. Assuming I have a square root s of -2 mod (n), I just do s+1 and I'm done! Let's try this for a few different n, including of course n=9. solve_mod([x^2==-2],9)  [(4,), (5,)] [(4,), (5,)] Should you not particularly enjoy completing the square, here is the basic idea. The key thing to keep in mind is that we do not actually divide by 2a, but instead multiply by (2a)^{-1}. • ax^2+bx+c\equiv 0 • 4a^2x^2+4abx+4ac\equiv 0 • (2ax+b)^2-b^2+4ac\equiv 0 • (2ax+b)^2\equiv b^2-4ac So to solve, we'll need that 2a is a unit (such as if n is odd), and then to find all square roots of b^2-4ac in \mathbb{Z}_n. Then the solution to$$ax^2+bx+c\equiv 0\text{ mod }(n)$$is actually$$x\equiv(2a)^{-1}(s-b)\text{ mod }(n)\text{, where }s^2\equiv b^2-4ac\text{ mod }(n)$$which in particular means that$$gcd(2a,n)=1\text{ must be true and that }s^2\equiv b^2-4ac\text{ must have a solution.}$$Example: Let's do all this with x^2+3x+5\equiv 0 mod(n). Notice that b^2-4ac=9-20=-11, so this equation does NOT have a solution over the integers, or indeed over the real numbers. Does it have a solution in \mathbb{Z}_n for some n, though? [(n,solve_mod([x^2==-11],n)) for n in range(2,20)]  \begin{array}{l}[\left(2, \left[\left(1\right)\right]\right),\\ \left(3, \left[\left(1\right), \left(2\right)\right]\right),\\ \left(4, \left[\left(1\right), \left(3\right)\right]\right),\\ \left(5, \left[\left(2\right), \left(3\right)\right]\right),\\ \left(6, \left[\left(1\right), \left(5\right)\right]\right),\\ \left(7, \left[\right]\right),\\ \left(8, \left[\right]\right),\\ \left(9, \left[\left(4\right), \left(5\right)\right]\right),\\ \left(10, \left[\left(3\right), \left(7\right)\right]\right),\\ \left(11, \left[\left(0\right)\right]\right),\\ \left(12, \left[\left(1\right), \left(5\right), \left(7\right), \left(11\right)\right]\right),\\ \left(13, \left[\right]\right),\\ \left(14, \left[\right]\right),\\ \left(15, \left[\left(2\right), \left(7\right), \left(8\right), \left(13\right)\right]\right),\\ \left(16, \left[\right]\right),\\ \left(17, \left[\right]\right),\\ \left(18, \left[\left(5\right), \left(13\right)\right]\right),\\ \left(19, \left[\right]\right)]\end{array} \begin{array}{l}[\left(2, \left[\left(1\right)\right]\right),\\ \left(3, \left[\left(1\right), \left(2\right)\right]\right),\\ \left(4, \left[\left(1\right), \left(3\right)\right]\right),\\ \left(5, \left[\left(2\right), \left(3\right)\right]\right),\\ \left(6, \left[\left(1\right), \left(5\right)\right]\right),\\ \left(7, \left[\right]\right),\\ \left(8, \left[\right]\right),\\ \left(9, \left[\left(4\right), \left(5\right)\right]\right),\\ \left(10, \left[\left(3\right), \left(7\right)\right]\right),\\ \left(11, \left[\left(0\right)\right]\right),\\ \left(12, \left[\left(1\right), \left(5\right), \left(7\right), \left(11\right)\right]\right),\\ \left(13, \left[\right]\right),\\ \left(14, \left[\right]\right),\\ \left(15, \left[\left(2\right), \left(7\right), \left(8\right), \left(13\right)\right]\right),\\ \left(16, \left[\right]\right),\\ \left(17, \left[\right]\right),\\ \left(18, \left[\left(5\right), \left(13\right)\right]\right),\\ \left(19, \left[\right]\right)]\end{array} So we really just need to look at square roots. And that's what we'll start with next time! Homework, including from last time: 1. Tell me what day you are presenting AS SOON AS YOU READ THIS! 2. Show that x^3=y^2-999 has no integer solutions. 3. Show that the Pell equation x^2-dy^2=1, where d is a perfect square, has just two solutions. 4. Look up the current best known bound on the number of integer points on a Mordell equation curve. 5. 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\; .$$6. 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. 7. 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. 8. 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. 9. 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.
10. For what $n$ does $-1$ have a square root modulo $n$?  (Hint: prime factorization and the previous problem.)
11. Clearly $4$ has a square root modulo $7$.  Find all square roots of $4$ modulo $7^3$ without using Sage or trying all $343$ possibilities.
12. Solve $x^2+3x+5\text{ mod }(15)$ using completion of squares and trial and error for square roots to confirm the computation above.
13. Solve the following congruences without using a computer:
• $x^2+6x+5$ mod (17)
• $5x^2+3x+1$ mod (17)
14. Read Chapter 7 through Example 7.6, including looking at (but not necessarily doing) all exercises; we will cover this material next time, but I will assume you are relatively familiar with the terminology and notation when we start.