# MAT 338 Day 23 2011

## 2436 days ago by kcrisman

Today will be as action-packed as last time was leisurely.   We're going to prove just what numbers are in $S_2$!

We will begin by using an identity from last time in a surprising way to talk about how many ways we can write some numbers as a sum of squares.

Sidebar:  We will connect sums of squares to factorization. Remember that the Brahmagupta-Fibonacci identity says that if two numbers are in $S_2$, so is their product.  Remarkably, we can sort of do this backwards:  $$\text{If an odd number }N\in S_2\text{ in two different (positive) ways, then }N=yz\text{ where }y,z>1\text{ and }y,z\in S_2\; .$$  That is, not a situation like $$13=3^2+2^2=2^2+3^2$$ but where $$25=5^2+0^2=3^2+4^2\; .$$  Assuming that $$N = a^2+b^2 = c^2+d^2\text{ with }a,c\text{ odd and }b,d\text{ even,}$$then let $$k=gcd(a-c,d-b)\text{ and }n=gcd(a+c,d+b)\text{ (both are even)}$$ and $$\ell=\frac{a-c}{k}=\frac{d+b}{n}\text{ and }m=\frac{a+c}{n}=\frac{d-b}{k}$$ and we get that $$N=\left[\left(\frac{k}{2}\right)^2+\left(\frac{n}{2}\right)^2\right]\left(m^2+\ell^2\right)$$  There are some details here, especially in terms of verifying all these numbers exist, but they are mostly just the definition of gcd and parity.

So for instance for $N=25$, $k=gcd(2,4)=2$, $n=gcd(8,4)=4$ which means $\ell=1$ and $m=2$, yielding $$25=\left[\left(\frac{2}{2}\right)^2+\left(\frac{4}{2}\right)^2\right]\left(1^2+2^2\right)=5\cdot 5$$ and so $25$ is a product of numbers themselves writeable as a sum of two squares.

Fact:  It is now trivial to prove that a prime is writeable in zero or one (positive) way as a sum of two squares.

Proof: This is clear for $p=2$, and we proved it above if $p\equiv 3\text{ mod }(4)$.  If $p\equiv 1\text{ mod }(4)$, then if $p$ is writeable in two different ways, it factors.  But prime numbers don't factor nontrivially.  So there is just one way to do it.

We can see this visually, in that each of circles with radius square root a prime either has no lattice points, or has only positive lattice points that are $(a,b)$ and $(b,a)$ for one $a$ and $b$.

var('x,y') @interact def _(n=(5,prime_range(150))): viewsize=ceil(math.sqrt(n))+.5 g(x,y)=x^2+y^2 p = implicit_plot(g-n,(-1,viewsize),(-1,viewsize),plot_points = 100) lattice_pts = [[i,j] for i in [-1..viewsize] for j in [-1..viewsize]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) curve_pts = [coords for coords in lattice_pts if g(coords[0],coords[1])==n] if len(curve_pts)==0: show(p+plot_lattice_pts, figsize = [5,5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize, aspect_ratio=1) else: plot_curve_pts = points(curve_pts, rgbcolor = (0,0,1),pointsize=20) show(p+plot_lattice_pts+plot_curve_pts, figsize = [5,5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize, aspect_ratio=1)

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

Next, we'll start out with our formal investigation of what numbers are in $S_2$ by taking a look at a lemma seemingly unrelated to writing things as sums of squares.

Recall:  We say that a number $a$ has a square root modulo $n$ if there is some number $x$ with $$x^2\equiv a\text{ mod }(n)\; .$$

We discussed this a fair amount, such as finding square roots of $\pm 1$ earlier.  Here is a fact we mentioned before.

Fact: For an odd prime $p$, then the only way there is a square root of $-1$ modulo $p$ is if $p\equiv 1\text{ mod }(4)$.

Remember, this means there can't be one if $p\equiv 3\text{ mod }(4)$, and that there might be one if $p\equiv 1\text{ mod }(4)$.

This should be at least vaguely plausible as being connected to sums of squares, because last time we saw that square roots of negative one in $\mathbb{Z}$ (not $\mathbb{Z}_n$) were connected to sums of squares.

There are a lot of ways to prove this fact, but the easiest is to use our knowledge of groups.  If $$u^2\equiv -1\text{ mod }(p)$$ then then order of $u$ in $U_p$ is four, since $$u^4=(u^2)^2\equiv (-1)^2=1\; .$$  We know that the order $$\mid U_p \mid =p-1$$ but then Lagrange's Theorem (the group theory one) says that four divides $p-1$.  So the only possible such prime $p$ is one that is of the form $4k+1$.  (We used the fact that $p$ is odd because then $-1\not\equiv +1$.)

Now we get to our lemma.

Lemma: If $p\equiv 1\text{ mod }(4)$, then there actually does exist a square root of $-1$ modulo $p$.

That is, there is a $u$ such that $$u^2\equiv -1\text{ mod }(p)\; .$$

Proof: This is something we could have done immediately after Wilson's Theorem, so we'll start with the proof of that.

Recall that in Wilson's Theorem, we showed that $(p-1)!\equiv -1$ mod ($p$) by pairing up all the numbers from $2$ to $p-2$ in pairs of multiplicative inverses mod ($p$), thus: $$(p-1)!=1\cdot 2\cdot 2^{-1}\cdot 3\cdot 3^{-1}\cdots (p-1) \equiv (p-1)\equiv -1\text{ mod (}p)\, .$$  Now, assuming that Wilson's Theorem is true, we will pair up the numbers from $1$ to $p-1$ in a different way, in pairs of additive inverses mod ($p$):  $$(p-1)!=1\cdot (p-1)\cdot 2\cdot (p-2)\cdot 3\cdot (p-3)\cdots \frac{p-1}{2}\cdot\frac{p+1}{2}=\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\cdot \left[(p-1)\cdot (p-2)\cdots \frac{p+1}{2}\right]\, .$$  This makes sense because $(p-1)/2$ is an integer halfway between $1$ and $p$, as $p$ is odd.

But if we rethink things mod ($p$), we can rewrite this in a more suggestive way.  Let $\left(1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right)$ be called $f$ (this is also $\left(\frac{p-1}{2}\right)!$, of course):  $$\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\cdot \left[(p-1)\cdot (p-2)\cdots \frac{p+1}{2}\right]\equiv f \cdot \left[-1\cdot -2\cdot -3\cdot -\frac{p-1}{2}\right]$$ $$\equiv f\cdot (-1)^{\frac{p-1}{2}}\left[1\cdot 2\cdot 3\cdots \frac{p-1}{2}\right]\equiv (-1)^{\frac{p-1}{2}}f^2\, .$$  Now, when $p\equiv 1$ mod (4), then $p=4k+1$ so $\frac{p-1}{2}=2k$ is even.  That means: $$-1\equiv f^2\text{ or }f^2\equiv -1\text{ mod }(p)$$ so in fact there precisely two square root of negative one (as Lagrange's Theorem suggests), $\pm \left(\frac{p-1}{2}\right)!$ - somehow a satisfying answer.

We can check that these really are square roots of $-1$.

@interact def _(p=(13,[q for q in prime_range(200) if q%4==1])): k=mod(factorial((p-1)/2),p) html("The potential square roots of $-1$ are $\pm \left(\\frac{%s-1}{2}\\right)!=%s,%s\\text{ mod }(%s)$"%(p,k,-k,p)) html("And we can compute that ${0}^2\equiv{1}$ and ${2}^2\equiv {3}$ modulo ${4}$".format(k,k^2,-k,(-k)^2,p))

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

We will use this lemma to prove our conjecture from last time - that every odd prime of the form $p=4k+1$ can be represented as the sum of two squares!    Then we'll combine it with the observation about primes of the form $p=4k+3$ to see exactly which numbers can be thus represented.

First, let's look at the following diagram.

var('x,y') @interact def _(p=(5,[q for q in prime_range(200) if q%4==1])): u=mod(factorial((p-1)/2),p) viewsize=ceil(math.sqrt(p))+2 g(x,y)=x^2+y^2 plot1 = implicit_plot(g-p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) 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[1]-u*coords[0])%p==0] 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

As you can see, I am plotting certain points on the circle $x^2+y^2=n$, with $n=5$ to begin.  I have done some 'magic' to turn the square root of $-1\text{ mod }(n)$ into these points.  Before telling you the magic, let's get ready to see it.

• More precisely, I've used this square root of $-1$ to create the regularly spaced grid of blue points.  See below.
• You can think about it as a bunch of corners of parallelograms.   (Sometimes we generically call things like the set of blue dots a lattice, though we won't need to know that - we will usually use the word lattice only to refer to the integer lattice of the black dots.)
• As one final preliminary, for any old point $(x,y)$ in the integer lattice, but especially for our blue dots, let's define one more thing - the norm of the point, $N(x,y)=x^2+y^2$.  (This norm, used on the complex number $x+yi$, is the way one can use the Euclidean algorithm on Gaussian integers, by the way.)

How are we defining the points?

• Assuming that $p$ is our prime and $k=\left(\frac{p-1}{2}\right)!$ is our square root of negative one;
• They all are of the form $(a,ak+bp)$ for all integers $a,b$.
• (This is an example like vectors generated by a basis, for those who have had linear algebra - except instead of being vectors over $\mathbb{Q}$ or $\mathbb{R}$, they are over $\mathbb{Z}$.)

Proof: Now we want to prove that every prime of this form can be written as a sum of squares.  Here is the strategy.

• Suppose we find some blue dot $(a,ak+bp)$ such that $$0<N(a,ak+bp)=a^2+(ak+bp)^2<2p\, .$$
• Then we know, modulo $p$, that $$N(a,ak+bp)=a^2+(ak+bp)^2 \equiv a^2+(ak)^2\equiv a^2+a^2 k^2\equiv a^2-a^2\equiv 0\text{ mod (}p)\, ,$$ so $p$ in fact divides the norm of the point $(a,ak+bp)$.
• So we have that $0<a^2+(ak+bp)^2<2p$ and that $p\mid a^2+(ak+bp)^2\cdots$
• So the only possibility is that $p=a^2+(ak+bp)^2$, which gives $p$ explicitly written as a sum of squares.

For instance, with $p=5$, we have that $k=\left(\frac{5-1}{2}\right)!=2!=2$, so we need to find a point $(a,2a+5b)$ such that $a^2+(2a+5b)^2<2p$.  Guess and check with $a=1$ and $b=0$ gives us $$N(1,2\cdot 1 +5\cdot 0)=1^2+(2\cdot 1+5\cdot 0)^2=5<2\cdot 5=10$$ so this point should work, and this does give the correct statement that $$5=1^2+2^2\; .$$

So what remains to be shown is that there actually IS such a blue dot.

@interact def _(p=(5,[q for q in prime_range(200) if q%4==1])): u=mod(factorial((p-1)/2),p) viewsize=p g(x,y)=x^2+y^2 plot1 = implicit_plot(g-p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) plot2 = implicit_plot(g-2*p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) 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[1]-u*coords[0])%p==0] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=10) show(plot1+plot2+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

We need to prove there is a blue dot (somewhere) that is not at the origin but also has norm smaller than $2p$ (remember the inequality above).  The bigger circle is the one we care about now - it has formula $x^2+y^2=2p$, so radius $\sqrt{2p}$.  If we find a blue point inside that circle but not at the origin, then the above argument proves it must be on the smaller circle.

Key idea: Area!

It will turn out that the best way to do this is by considering the areas of the various circles, and showing that they are so big you just must have a blue point in it (but not at the origin).

The area of the bigger circle, which has radius $\sqrt{2p}$, is $\pi (\sqrt{2p})^2=2\pi p$.  Since $\pi >2$, we have that $2\pi>2(2)=4$, which mean that the area of the bigger circle is bigger than $4p$.

@interact def _(p=(5,[q for q in prime_range(200) if q%4==1]),triangles_on=False): u=mod(factorial((p-1)/2),p) viewsize=2*p g(x,y)=x^2+y^2 plot1 = implicit_plot(g-p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) plot2 = implicit_plot(g-2*p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) plot3 = line([[0,0],[2*p-2*Integer(u),2],[2*p,0],[2*Integer(u),-2],[0,0]],rgbcolor=(1,0,0)) plot4 = line2d([[0,0],[2*p,0]],rgbcolor=(1,0,0),linestyle='--') 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[1]-u*coords[0])%p==0] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=10) plot_lattice_pts2 = points([[2*coords[0],2*coords[1]] for coords in lattice_pts], rgbcolor = (0,1,0),pointsize=20) if triangles_on: show(plot1+plot2+plot3+plot4+plot_grid_pts+plot_lattice_pts+plot_lattice_pts2, xmin = -viewsize/2, xmax = viewsize, ymin = -viewsize/2, ymax = viewsize/2, aspect_ratio=1) else: show(plot1+plot2+plot_grid_pts+plot_lattice_pts+plot_lattice_pts2, xmin = -viewsize/2, xmax = viewsize, ymin = -viewsize/2, ymax = viewsize/2, aspect_ratio=1)

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

What we do now is to create a sublattice of the blue dots.  Take all blue dots, and just double their coordinates; this will give you the green dots above.  (Naturally, underneath each green dot is a blue dot.)   Now we take a look at the triangles made by the green dots.

• You should see that the thinnest triangle made by the green dots has height $2p$ (from the origin to $(2p,0)$, which has $a=1$ and $b=0$, then doubled) and base $2$ (to the point $(2k,2)$, which has $a=0$ and $b=1$ doubled again).
• You can click on 'triangles_on' above to see them in red.
• This triangle has area $4p/2$ - so the parallelogram with the solid red lines has area $4p$.  So it's smaller than the bigger circle!
• Finally, note that the green points repeat in parallelograms like this every time you move outside this particular parallelogram, infinitely often.

This proof is very visual, so before we move on, make sure you believe all of this.  Then we will analyze the exact areas involved more closely to finish.  Remember, we are trying to prove that there is a blue point inside the bigger blue circle, but away from the origin.

@interact def _(p=(5,[q for q in prime_range(200) if q%4==1])): u=mod(factorial((p-1)/2),p) viewsize=2*p g(x,y)=x^2+y^2 plot1 = implicit_plot(g-p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) plot2 = implicit_plot(g-2*p,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) plot3 = line([[0,0],[2*p-2*Integer(u),2],[2*p,0],[2*Integer(u),-2],[0,0]],rgbcolor=(1,0,0)) plot4 = line2d([[0,0],[2*p,0]],rgbcolor=(1,0,0),linestyle='--') 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[1]-u*coords[0])%p==0] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=10) plot_lattice_pts2 = points([[2*coords[0],2*coords[1]] for coords in lattice_pts], rgbcolor = (0,1,0),pointsize=20) show(plot1+plot2+plot3+plot4+plot_grid_pts+plot_lattice_pts+plot_lattice_pts2, xmin = -viewsize/2, xmax = viewsize, ymin = -viewsize/2, ymax = viewsize/2, aspect_ratio=1)

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

Let's look at the picture again.

• The area of the circle is more than the area ($4p$) of the parallelogram.
• Since all points inside the parallelogram (not just green, blue, or lattice points) repeat outside of it, $4p$ is the biggest area you can have and not repeat some point.
• So, the circle, having a bigger area, must have two points (not necessarily blue points, just points on the plane) which are repeated by the shifting of this parallelogram (called a fundamental region).
• This may sound a little suspicious, so let's be sure about it.
• Call the parallelogram in red $L$.
• The circle is composed of all the pieces of the circle in different parallelograms of green dots congruent to $L$.
• We can move the pieces in the circle to the corresponding part of $L$.
• Suppose there aren't two points which are repeated in the big circle.  Then this movement of pieces of the circle to $L$ is one-to-one.
• But if that is one-to-one, then the pieces of the circle must at most fill up $L$.
• However, the circle has a bigger area than $L$!  This is not possible, since moving doesn't change area, and thus there are two points which are repeated.
• Take two points that are repeated in the circle - say $v$ and $w$.  Then $v-w$ (if we consider them as vectors) is actually a green point, since the difference one shifts them by must be one of the obvious directions of the parallelogram.
• That means the point $(v-w)/2$ is a blue point, and it's not the origin!
• Further, this blue point is inside the big circle.
• Since the circle is nicely symmetric about the origin, the point $-w$ is also in the circle.
• The midpoint of the line segment connecting $v$ and $-w$, both points in the big circle, is in fact $(v-w)/2=\frac{v+(-w)}{2}$.
• So it's in the big circle, and we have found a blue point other than the origin in the blue circle.

That's the proof! Hooray! Whew!

Here is a picture of how to find the blue point in the circle.  The black points are $v$, $w$, and $-w$, and you see the midpoint of the line is indeed blue.

v=point((Integer(u)+1,-1),pointsize=20,rgbcolor=(0,0,0)) w=point((-Integer(u)+1,1),pointsize=20,rgbcolor=(0,0,0)) z=point((Integer(u)-1,-1),pointsize=20,rgbcolor=(0,0,0)) plot5=line([[Integer(u)+1,-1],[Integer(u)-1,-1]],rgbcolor=(0,0,0)) plot6=point((Integer(u),-1),pointsize=20) show(plot1+plot2+plot3+plot4+v+w+z+plot5+plot6+plot_grid_pts+plot_lattice_pts+plot_lattice_pts2, figsize = [5,5], xmin = -viewsize/2, xmax = viewsize, ymin = -viewsize/2, ymax = viewsize/2, aspect_ratio=1)

There are lots of other points of view of this theorem, which indicates its importance.

1. As a handout, I have a (relatively famous) completely different proof - the only one I have ever seen that does not require square roots of $-1$ modulo $p$.
2. See how square roots of negative one show up here?  So, as we mentioned last time, it really shouldn't be surprising that "prime numbers" in the $$\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}\, ,$$ defined with the integer square root of negative one, are closely related.
• Proofs that use this rely strongly on the fact that the Bezout identity and the Euclidean algorithm hold in the Gaussian integers.  Namely:
• You can write two Gaussian integers $a$ and $b$ as $a=bq+r$, where $0\leq N(r)<N(b)$, and this process ends by well-ordering, and can define $gcd(a,b)$.  In this case $\pm 1$ and $\pm i$ are all possible stopping points if $a$ and $b$ don't share a factor.
• If $g$ and $h$ are 'relatively prime' Gaussian integers ($gcd(g,h)=\pm 1$ or $\pm i$), then there are other such integers $x$ and $y$ such that $gx+hy=1$.

Unfortunately, Sage does not have this implemented in a user-friendly format.  This is mostly because the naive things one might do are tricky to get to work nicely with the not-so-naive things professional number theorists need factorization in general algebraic structures coming from the complex numbers to do.

gcd(2,3+3*i)
 Traceback (click to the left of this block for traceback) ... TypeError: unsupported operand parent(s) for 'xgcd': 'Integer Ring' and 'Symbolic Ring' Traceback (most recent call last): File "", line 1, in File "/Users/karl-dietercrisman/.sage/sage_notebook/worksheets/admin/69/code/5.py", line 7, in xgcd(_sage_const_2 ,_sage_const_3 +_sage_const_3 *i) File "/Users/karl-dietercrisman/Desktop/sage-3.4/local/lib/python2.5/site-packages/SQLAlchemy-0.4.6-py2.5.egg/", line 1, in File "/Users/karl-dietercrisman/Desktop/sage-3.4/local/lib/python2.5/site-packages/sage/rings/arith.py", line 1434, in xgcd return a.xgcd(b) File "element.pyx", line 1951, in sage.structure.element.PrincipalIdealDomainElement.xgcd (sage/structure/element.c:11756) File "coerce.pyx", line 740, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:5848) TypeError: unsupported operand parent(s) for 'xgcd': 'Integer Ring' and 'Symbolic Ring'

There is one loose end.  Namely, why is it that there are some composite numbers of the form $4k+1$ which are not in $S_2$ - and which even numbers are in $S_2$?

• First, what if $N$ has only primes of the form $4k+1$ and $2$ as factors?
• Then each of those primes is in $S_2$, so we can use the Brahmagupta-Fibonacci identity to write the intermediate products that way.
• E.g., $$2\cdot 13\cdot 17=442 = \left(1^2+1^2\right)\left( 3^2+2^2\right)\cdot 17 = \left[\left(1\cdot 3-1\cdot 2\right)^2+\left(1\cdot 2+1\cdot 3\right)^2\right]\left(4^2+1^2\right)$$ $$=\left(1^2+5^2\right)\left(4^2+1^2\right)=\left(1\cdot 4-5\cdot 1\right)^2+\left(1\cdot 1+5\cdot 4\right)^2=1^2+21^2$$
• Next, what if $N$ has primes of the form $4k+3$, but only to even powers?
• We saw last time that $p^2$ is always in $S_2$ trivially, since $p^2=p^2+0^2$.
• So for each factor of $p^2$, we can do this again.  In fact, we just have to multiply each term by $p^2$!
• E.g., $$35802=442\cdot 3^4 = \left(1^2+21^2\right)3^2\cdot 3^2=1^2\cdot 3^2\cdot 3^2+21^2\cdot 3^2\cdot 3^2=9^2+189^2$$
• What if $N$ had a prime of the form $p=4k+3$ to an odd power?
• This seemed to be the bottleneck in our exploration.
• Suppose that it is possible to write $$N=a^2+b^2\; .$$
• Divide this equation by any factors of $p$ common to both sides to get $$M=c^2+d^2\, .$$  (This must actually be an even power of $p$, since the right-hand side is made up of squares and can only contribute even powers of primes.)
• Now $M$ still has an odd power of $p$ dividing it, but $p\nmid c,d$.  Take everything modulo $p$ to get $$0\equiv c^2+d^2\text{ mod }(p)\; .$$
• Since $p \nmid c$, we can multiply this congruence by $\left(c^{-1}\right)^2$ to get $$0\equiv 1+\left(c^{-1}\right)^2d^2\Rightarrow -1\equiv \left(c^{-1}d\right)^2\text{ mod }(p)$$
• There is no square root of $-1$ modulo $p$, however, so our supposition that $N=a^2+b^2$ is impossible.

As a result, we have proved a Theorem:

$N$ is in $S_2$ precisely if it has only even powers (including zeroth powers) of any primes of the form $4k+3$.

factor(21);two_squares(21)
 3 * 7 Traceback (click to the left of this block for traceback) ... ValueError: 21 is not a sum of two squares 3 * 7 Traceback (most recent call last): File "", line 1, in File "_sage_input_35.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("ZmFjdG9yKDIxKTt0d29fc3F1YXJlcygyMSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/private/var/folders/Yy/YytEJm5VEB0+pBRD7JNLe++++TQ/-Tmp-/tmpizm9tE/___code___.py", line 3, in exec compile(u'factor(_sage_const_21 );two_squares(_sage_const_21 ) File "", line 1, in File "/Applications/MathApps/sage/local/lib/python2.6/site-packages/sage/rings/arith.py", line 4350, in two_squares raise ValueError, "%s is not a sum of two squares"%n ValueError: 21 is not a sum of two squares

The homework, which is last time's plus some new ones:

1. Prove that if $n\equiv 3\text{ mod }(4)$, then $n$ cannot be written as a sum of two squares.
2. Read Section 10.3 in the book; the notation $S_3$ describes the set of integers writeable as a sum of three squares, as $S_2$ might indicate the set of things writeable as the sum of two squares.  Do Exercises 10.9-10.12.
3. Find as many integers $n$ as possible which are only writeable as a sum of squares via $n=a^2+a^2=2a^2$, i.e. $n$ is not writeable as a sum of distinct squares.
4. Verify the Brahmagupta-Fibonacci identity by hand (i.e. write all the algebra out).
5. Let $r_2(n)$ be the number of different ways to write $n$ as a sum of squares, where every different way is counted. For instance, $$r_2(2)=4\text{ because }(-1,1),(-1,-1),(1,1),(1,-1)\text{ all work.}$$  Prove that $$r_2\left(2^n\right)=4\text{ for all }n\; .$$
6. Let $N$ be odd, and let $N=a^2+b^2$ and $N=c^2+d^2$, where the pairs $(a,b)$ and $(c,d)$ are both positive and not the same or just switched in order.  Verify the following:
• It's okay to assume that $a$ and $c$ are odd and $b$ and $d$ are even.
• If this is the case, show that $k=gcd(a-c,b-d)$ and $n=gcd(a+c,b+d)$ are both even.
• Then show that $\frac{a-c}{k}=\frac{b+d}{n}$ and $\frac{b-d}{k}=\frac{a+c}{n}$.
• Finally, show that neither factor of $N$ we get is trivial (i.e., 1).
7. Pick four random (to you) three digit numbers which are not of the form $4k+3$ and decide whether they are a sum of two squares.
8. Pick two of the ones above which are a sum of two squares and write them in all possible ways as a sum of squares.
9. Show a positive integer $k$ is the difference of two squares if and only if $k\not \equiv 2$ mod (4).  (Hint: Our Fermat stuff and why it ends...)
10. Look up the concepts of "Gaussian moat" and "Gaussian zoo" online and see what you think!
11. Prove that if $n\equiv 12$ mod (16), show that $n$ cannot be written as a sum of two squares.
12. Is there any congruence condition modulo $6$ for which a number cannot be written as a sum of two squares?
13. Read through the end of Section 10.2 and look especially at Examples 10.4 and 10.8, and then do Exercises 10.2, 10.3, 10.6, and 10.7.
14. Check that the pictures you get from some other primes with these lattices really work.
15. Check every piece of the Zagier proof:
• The set $S$ is finite.  Try figuring out what $S$ is for $p=5$ or $p=13$, the smallest such primes.
• Each $(x,y,z)$ has exactly one of the three things to go to.
• If you take the output and apply the function again, you get $(x,y,z)$ back (this is a little tougher).
• If $(x,y,z)$ goes to $(x,y,z)$ then it turns out that $(x,y,z)=(1,1,\frac{p-1}{4})$ (you will probably need to use the definition of $S$ for this, and remember that we assume $p\equiv 1$ mod (4)).
• That if the map $(x,y,z)\to (x,z,y)$ has a point which is fixed (the output is same as input) then this, combined with the definition of $S$, means that $p$ is writeable as the sum of two squares.