Recall that last time we saw that if we
we will always get a rational point, and often an integer point!
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 socalled Pell equations like $$x^22y^2=1$$ These were already rigorously discussed by Brahmagupta, as I mentioned before  clearly a quite old idea!
For instance, $x^22y^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.
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^22y^2=1$, as well as (along the way) approximations to the square root of $2$.
Now let's try this with actual points!
Click to the left again to hide and once more to show the dynamic interactive window 
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^22y^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^22y^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.
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^23y^2=1$ with $$2^23\cdot 1^2=1\; .$$
That is, I use $$x'=x^2+3y^2\text{ and }y'=2xy$$
7^23\cdot4^2=1
7^23\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^2ny_0^2=k\text{ and }x_1^2ny_1^2=\ell$$ $$\text{then }x=x_0x_1+ny_0y_1,\; y=x_0y_1+y_0x_1\text{ solves }x^2ny^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:
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^292y^2=1$ within a year proved the person "was a mathematician", we can be very thankful for computers!
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{p1}{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 nonprime moduli. We can ask Sage about this:
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.
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:
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.
[(5,), (6,)] [(5,), (6,)] 
This shows that $x^22x+3\equiv 0$ mod (9) has two solutions. How might I solve a general quadratic congruence?
Example:
The key is completing the square! $$x^22x+3=\left(x^22x+\left(\frac{2}{2}\right)^2\right)+3\left(\frac{2}{2}\right)^2=(x1)^2+2\, ,$$ so $$(x1)^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$.
[(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}$.
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^24ac$ in $\mathbb{Z}_n$.
Then the solution to $$ax^2+bx+c\equiv 0\text{ mod }(n)$$ is actually $$x\equiv(2a)^{1}(sb)\text{ mod }(n)\text{, where }s^2\equiv b^24ac\text{ mod }(n)$$ which in particular means that $$gcd(2a,n)=1\text{ must be true and that }s^2\equiv b^24ac\text{ must have a solution.}$$
Example:
Let's do all this with $x^2+3x+5\equiv 0$ mod($n$). Notice that $b^24ac=920=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?
\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:
