MAT 338 Day 4 2011

2427 days ago by kcrisman

Today is all about more issues regarding integers - no primes, no modulo, just integers - and we will continue the point of view of the integer lattice to frame our thoughts.  

But first, I just have to be gratuitous; try evaluating this next cell, and seeing whether you can get a GCD which is not 3...

@interact def _(m=(3,[1..20]),n=(2,[1..20])): html("The gcd of $%s$ and $%s$ is $%s$"%(5*10^m+1,5*10^n+1,gcd(5*10^m+1,5*10^n+1))) 
       

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

Do you think this pattern continues?  It's an interesting question$\ldots$

Also, I want to kill the suspense on the conductor.  

  • The conductor of $a$ and $b$, sometimes denoted $\kappa(a,b)$, is $(a-1)(b-1)$.
  • So $ab-a-b$ really is the biggest one we can't do.
  • Furthermore, exactly half of the numbers $n$ between $0\leq n\leq \kappa(a,b)$ are actually representable.  

A very neat solution!  Proving all this about it is a little tedious with the tools we have at hand, though.  Remember, for the one you did, you had to work with all the remainders with respect to four or three, and extending that in general is a mouthful.  Soon we'll return to it for an easier proof, I promise!

Okay, now to integer lattice points/integer-only number theory.  Let's review what was on the last homework assignment.

  • How many positive integer solutions to $ax+by=c$ are there?
@interact def _(a=slider(1,20,1,1),b=slider(1,20,1,1),c=slider(1,20,1,4)): ym = c/b + 1 xm = c/a + 1 p = plot(-(a/b)*x+c/b,-1,xm, plot_points = 200) lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) if mod(c,gcd(a,b))==0: line_pts = [coords for coords in lattice_pts if (coords[0]>0) and (coords[1]>0) and (a*coords[0]+b*coords[1]==c)] if len(line_pts)==0: html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('No positive lattice points at all!') show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) else: plot_line_pts = points(line_pts, rgbcolor = (0,0,1),pointsize=20) html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('Number of positive lattice points = ' + str(len(line_pts))) show(p+plot_lattice_pts+plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) else: html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('No positive lattice points at all!') show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) 
       

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

What we are really asking is how many integer lattice points lie between the intercepts.  One way to think about this is the distance between solutions.  Let's assume that the equation is $ax+by=c$, and $gcd(a,b)=1$.  Then from solution $(x_0,y_0)$ we get solution $(x_0+b,y_0-a)$, and the distance between any two solutions is $$\sqrt{[(x_0+b)-x_0]^2+[(y_0-a)+y_0]^2}=\sqrt{a^2+b^2}\, .$$  Our strategy is now to see how many times that distance fits between the intercepts of the line - does that make sense?  It doesn't give an exact answer, but should give a good ballpark estimate.

Those intercepts are $\frac{c}{a}$ and $\frac{c}{b}$, respectively (check it out above e.g. with $a=3$, $b=2$, $c=4$).  Using the Pythagorean Theorem again, we see that the whole length available is $$\sqrt{\Big(\frac{c}{a}\Big)^2+\Big(\frac{c}{b}\Big)^2}=\frac{c}{ab}\sqrt{a^2+b^2}\, .$$  The ratio of this total length and the length between solutions is thus $\frac{c}{ab}$, which is a very nice pat answer.  

There are two problems with it, though! 

  1. There is no guarantee that $\frac{c}{ab}$ is an integer!  In fact, it usually won't be.  For instance, with $2x+3y=10$, $\frac{10}{2\cdot 3}\approx 1.67$.  So should the number of points be bigger than or less than this?
  2. Secondly, even so it's not clear what the precise connection between $\frac{c}{ab}$ and the actual number of points is.  $2x+3y=5$ has one, and $2x+3y=7$ has one, but $2x+3y=6$ doesn't - even though $\frac{c}{ab}$ is about one for all three of these.  In fact, the number of points is thus not even monotone with respect to $c$ increasing.

We can deal with each of these problems.  We'll want to introduce the greatest integer function to do so (also called the floor function).  Examples should suffice to define it: $$\lfloor 1.5\rfloor=1\; , \lfloor 1\rfloor=1\; ,\lfloor 1.99\rfloor=1\; ,\lfloor 0.99\rfloor=0\; ,\lfloor -.01\rfloor=-1\; .$$

  1. To rectify the integer problem, we will just consider $n=\lfloor \frac{c}{ab}\rfloor$, the greatest integer function applied to $\frac{c}{ab}$.
  2. Secondly, we simply recognize that there isn't a nice formula.  On average, we should expect $n$ lengths between integer points along the line segment in question (and hence as many as $n+1$ lattice points, since a partition of $n$ intervals has $n+1$ endpoints associated to it).  Here are some individual cases.
    1. How could the fewest of these appear?  That's when both the $x$- and $y$-intercepts are actually lattice points, because they do not have positive coordinates.  So if $c/a$ and $c/b$ are both integers, then we get precisely $\lfloor \frac{c}{ab}\rfloor-1$ lattice points.  This is the transition between $2x+3y=5$ to $2x+3y=6$.
    2. What if just one of the intercepts is a lattice point?  Then, beginning at that point, there is definitely room for the full $n$ lengths to appear - and you're guaranteed to get $n$ lattice points, because we just said the other intercept isn't a lattice point, so the $n$th one must appear before that point.  Compare $2x+3y=8$ and $2x+3y=9$ to the others above.
    3. Finally, if neither $c/a$ nor $c/b$ is an integer, then you get $n$ or $n+1$ lattice points.  There's no nice formula for this otherwise; but notice that with $2x+3y=11$ you do get $\lfloor \frac{11}{2\cdot 3}\rfloor+1=2$ positive lattice points!  (And it jumps back down to $\lfloor\frac{12}{2\cdot 3}\rfloor-1=1$ at $c=12$!
  3. That was all for $a$ and $b$ relatively prime.  If $gcd(a,b)\neq 1$, it is not too hard to show that any such line with respect to lattice points is the same as a line $a'x+b'y=c'$ for which $gcd(a',b')=1$; precisely which line is in your homework.

There are a lot of other interesting questions that one can ask about pure integers, and equations they might satisfy.  However, answering many of those questions will prove challenging without additional tools, so we will have to take a detour soon.  But one such question is truly ancient, and worth exploring more today.

It is also quite geometric.  We just used the Pythagorean Theorem above - but you'll note that we didn't really care whether the hypotenuse was an integer there.  Well, when is it?  More precisely, when are all three sides of a right triangle integers?

We call a triple of integers $x,y,z$ such that $x^2+y^2=z^2$ a Pythagorean triple, though there isn't necessarily evidence that Pythagoras thought this way about them.  However, Euclid certainly did, and so will we.  For that matter, we should also think of them as $x,y,z$ that fit on the quadratic curve $x^2+y^2=z^2$, given $z$ ahead of time.

 

@interact def _(z=(2,[1..100])): f(x,y)=x^2+y^2-z^2 max = z p = implicit_plot(f,(x,-1,max),(y,-1,max),plot_points = 200) lattice_pts = [[i,j] for i in [0..max] for j in [0..max]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) curve_pts = [coords for coords in lattice_pts if f(coords[0],coords[1])==0] if len(curve_pts)==0: show(p+plot_lattice_pts, figsize = [5,5], 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], aspect_ratio=1) 
       

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

It seems quite random for which $z$ we get a Pythagorean triple even existing!  (We'll return to that question later as well!)  First, let's see what triples are possible.

  • First, it turns out we really only need to worry about the case when $x,y,z$ are all relatively prime with each other.  If $x=x'a$ and $y=y'a$, for instance, then $$x^2+y^2=(x')^2a^2+(y')^2a^2=z^2$$ which means that $a^2|z^2$, and hence that $a|z$ as well.  (Notice that we haven't actually proved this last bit, but it should be familiar.)
  • Let's call Pythagorean triples where $gcd(x,y,z)=1$ primitive triples.  By the above, $x$ and $y$ can't both be even, but I claim they can't both be odd, either.  If they were, we would have $x=2k+1$ and $y=2\ell+1$ for some integers $k,\ell$, and then $$(2k+1)^2+(2\ell+1)^2=4\left(k^2+\ell^2+k+\ell\right)+2\; ;$$ and we saw a day or two ago that a perfect square ($z^2$) can't have remainder two when divided by four. 
  • So we assume that $x$ is odd and $y$ is even, without loss of generality (which means $z$ is odd).  Then let's look at the factorization $$z^2-x^2=(z-x)(z+x)\, .$$  Certainly $z-x$ and $z+x$ are both even, so that $z-x=2m$ and $z+x=2n$.    But since their product is a square ($y^2$), then $2m\cdot 2n=4mn$ is also a square, so $mn$ must be a square (a square divided by a square is a square of a rational number, and so this holds for integers if all three are integers).
  • Let's look at $m=\frac{z-x}{2}$ and $n=\frac{z+x}{2}$.  If they shared a factor, then $x=m+n$ and $z=n-m$ also share that factor.  But $gcd(x,z)=1$, so there are no such factors and $gcd\left(\frac{z-x}{2},\frac{z+x}{2}\right)=gcd(m,n)=1$ as well.  Letting $y=2j$, we see that $y^2=4mn$ yields $j^2=mn$, but that $m$ and $n$ are relatively prime!
  • Here we once again need some fact about squares and division we can't prove yet.  Namely, that if coprime integers make a square when multiplied, then they are each a perfect square.  So $m=p^2$ and $n=q^2$ for some integers (obviously coprime) $p$ and $q$.  This clearly implies that $j^2=p^2q^2$, so $y=2pq$.
  • Now we can put it all together.  $$z-x=2p^2,\; z+x=2q^2,\; \text{ and }y=2pq\, . $$ That is, $$z=p^2+q^2,\; x=q^2-p^2,\; \text{ and }y=2pq\; .$$ Since $x$ is odd, we now find another fact as well - that $p$ and $q$ cannot both be odd or both even (they have opposite parity).

So we can find all primitive Pythagorean triples by finding coprime integers $p$ and $q$ which have opposite parity, and then using this formula!  And we get all Pythagorean triples by multiplying.  Let's try to find some by hand now.

Of course, you could generate some as well...

n=10 Generators=[(p,q) for p in range(1,n) for q in range(p+1,n) if (gcd(p,q)==1) and not (mod(p,2)==mod(q,2))] for pairs in Generators: x=pairs[1]^2-pairs[0]^2;y=2*pairs[0]*pairs[1];z=pairs[0]^2+pairs[1]^2 print x,'squared plus',y,'squared is',z,'squared - ',x^2+y^2==z^2 
       
3 squared plus 4 squared is 5 squared -  True
15 squared plus 8 squared is 17 squared -  True
35 squared plus 12 squared is 37 squared -  True
63 squared plus 16 squared is 65 squared -  True
5 squared plus 12 squared is 13 squared -  True
21 squared plus 20 squared is 29 squared -  True
45 squared plus 28 squared is 53 squared -  True
77 squared plus 36 squared is 85 squared -  True
7 squared plus 24 squared is 25 squared -  True
55 squared plus 48 squared is 73 squared -  True
9 squared plus 40 squared is 41 squared -  True
33 squared plus 56 squared is 65 squared -  True
65 squared plus 72 squared is 97 squared -  True
11 squared plus 60 squared is 61 squared -  True
39 squared plus 80 squared is 89 squared -  True
13 squared plus 84 squared is 85 squared -  True
15 squared plus 112 squared is 113 squared -  True
17 squared plus 144 squared is 145 squared -  True
3 squared plus 4 squared is 5 squared -  True
15 squared plus 8 squared is 17 squared -  True
35 squared plus 12 squared is 37 squared -  True
63 squared plus 16 squared is 65 squared -  True
5 squared plus 12 squared is 13 squared -  True
21 squared plus 20 squared is 29 squared -  True
45 squared plus 28 squared is 53 squared -  True
77 squared plus 36 squared is 85 squared -  True
7 squared plus 24 squared is 25 squared -  True
55 squared plus 48 squared is 73 squared -  True
9 squared plus 40 squared is 41 squared -  True
33 squared plus 56 squared is 65 squared -  True
65 squared plus 72 squared is 97 squared -  True
11 squared plus 60 squared is 61 squared -  True
39 squared plus 80 squared is 89 squared -  True
13 squared plus 84 squared is 85 squared -  True
15 squared plus 112 squared is 113 squared -  True
17 squared plus 144 squared is 145 squared -  True

Historically, one of the big questions one could ask about such Pythagorean integer triangles was about its area.  For primitive ones, the legs must have opposite parity (do you remember why?), so the areas will be integers.  (For ones which are not primitive, the sides are multiples of sides with opposite parity, so they are certainly also going to have an integer area.)  

So what integers work?  You all know one with area 6, and it should be clear that ones with area 1 and 2 can't work (because the sides would be too small and because $2,1$ doesn't lead to a triple); can you find ones with other areas?  

n=10 Generators=[(p,q) for p in range(1,n) for q in range(p+1,n) if (gcd(p,q)==1) and not (mod(p,2)==mod(q,2))] for pairs in Generators: x=pairs[1]^2-pairs[0]^2;y=2*pairs[0]*pairs[1];z=pairs[0]^2+pairs[1]^2 print 'The primitive triple',x,y,z,'gives a triangle of area',x*y/2 
       
The primitive triple 3 4 5 gives a triangle of area 6
The primitive triple 15 8 17 gives a triangle of area 60
The primitive triple 35 12 37 gives a triangle of area 210
The primitive triple 63 16 65 gives a triangle of area 504
The primitive triple 5 12 13 gives a triangle of area 30
The primitive triple 21 20 29 gives a triangle of area 210
The primitive triple 45 28 53 gives a triangle of area 630
The primitive triple 77 36 85 gives a triangle of area 1386
The primitive triple 7 24 25 gives a triangle of area 84
The primitive triple 55 48 73 gives a triangle of area 1320
The primitive triple 9 40 41 gives a triangle of area 180
The primitive triple 33 56 65 gives a triangle of area 924
The primitive triple 65 72 97 gives a triangle of area 2340
The primitive triple 11 60 61 gives a triangle of area 330
The primitive triple 39 80 89 gives a triangle of area 1560
The primitive triple 13 84 85 gives a triangle of area 546
The primitive triple 15 112 113 gives a triangle of area 840
The primitive triple 17 144 145 gives a triangle of area 1224
The primitive triple 3 4 5 gives a triangle of area 6
The primitive triple 15 8 17 gives a triangle of area 60
The primitive triple 35 12 37 gives a triangle of area 210
The primitive triple 63 16 65 gives a triangle of area 504
The primitive triple 5 12 13 gives a triangle of area 30
The primitive triple 21 20 29 gives a triangle of area 210
The primitive triple 45 28 53 gives a triangle of area 630
The primitive triple 77 36 85 gives a triangle of area 1386
The primitive triple 7 24 25 gives a triangle of area 84
The primitive triple 55 48 73 gives a triangle of area 1320
The primitive triple 9 40 41 gives a triangle of area 180
The primitive triple 33 56 65 gives a triangle of area 924
The primitive triple 65 72 97 gives a triangle of area 2340
The primitive triple 11 60 61 gives a triangle of area 330
The primitive triple 39 80 89 gives a triangle of area 1560
The primitive triple 13 84 85 gives a triangle of area 546
The primitive triple 15 112 113 gives a triangle of area 840
The primitive triple 17 144 145 gives a triangle of area 1224

It is worth asking why there are no odd numbers in the list so far.  In fact, we can prove quite a bit about these things.

Remember, $x$ and $y$ can be written as $x=q^2-p^2$ while $y=2pq$, for relatively prime opposite parity $q>p$.  Then the area must be $$pq(q^2-p^2)=pq(q+p)(q-p)\, .$$  So can the area be odd?  

To find out more about what areas are possible, we show briefly that all four of the factors above are relatively prime to each other in pairs, at least in a primitive triple.  

  • $p$ and $q$ are.
  • $p$ and $p+q$ must be, since any factor they share is shared by $(p+q)-p=q$, but $gcd(p,q)=1$.
  • The same argument will work in showing that $p$ and $q-p$ are, as well as $q$ and either sum.
  • If $q+p$ and $q-p$ share a factor, it must be odd, and must be a factor of their sum and difference $2q$ and $2p$.  Since the putative factor is odd, it is coprime to $2$, and so we can use one of our corollaries to say that it is a factor of $p$ and $q$ as well, which is impossible.

So one could analyze a number to see if it is possible to write as a product of four relatively prime integers as a starting point.  E.g. $30=2\cdot 3\cdot 5\cdot 1$ is the only way to write $30$ as a product of four such numbers (assuming no more than one of those is 1!), and since $q+p$ must be the biggest, we must set $q+p=5$.  Quickly one can see that $q=3,p=2$ works with this, so there is such a triangle.  What are the sides?  

This turns out to be a very deep unsolved problem.  This article gives some background on the congruent number problem, which asks the related question of which Pythagorean triangles with rational side lengths give integer areas.  This page in particular is interesting from our present point of view.

But we can ask another question, which led Fermat to some of his initial investigations into this theory.  Namely, when is the area of a Pythagorean triple triangle a perfect square?  

@interact def _(n=20): Generators=[(p,q) for p in range(1,n) for q in range(p+1,n) if (gcd(p,q)==1) and not (mod(p,2)==mod(q,2))] list = [] for pairs in Generators: x=pairs[1]^2-pairs[0]^2;y=2*pairs[0]*pairs[1];z=pairs[0]^2+pairs[1]^2 if is_square(x*y/2): print html('The primitive triple $%s,%s,%s$ gives a triangle of square area $%s$'%(x,y,z,x*y/2)) list.append((x,y,z)) if not list: html("No triangles of square area up to $p,q\leq %s$!"%(n,)) 
       

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

If you'll notice, we don't see to be getting a lot of these.  In fact, none.

What would we need to do to investigate this?  Well, remember - we already did a lot of work in showing that the area is $$pq(q^2-p^2)=pq(q+p)(q-p)\; ,$$ where all four of those quantities are relatively prime.  If the area is also a perfect square, then (here's one of those unproved things again!) since they are coprime, they themselves are all perfect squares!

Now we will do something very clever.  Something the Greeks used occasionally; something Fermat used for many of his proofs.  We are going to take that (hypothetical) triangle, and produce a triangle with strictly smaller sides with the same properties - including integer sides and square area!  That means we could apply the same argument to our new triangle, and then the next one... but the Well-Ordering property won't allow that. So the original triangle was impossible to begin with.  

So let's make that smaller triangle!  

  • We know that $q+p$ and $q-p$ are (odd) squares - say $u^2$ and $v^2$.  That means that we can write $u$ and $v$ as $\frac{u+v}{2}+\frac{u-v}{2}$ and $\frac{u+v}{2}-\frac{u-v}{2}$ (which are integers since $u$ and $v$ are odd).  Letting $a=\frac{u+v}{2}$ and $b=\frac{u-v}{2}$, we have that $q+p=(a+b)^2$ and $q-p=(a-b)^2$.
  • Then a little algebra shows that $q=a^2+b^2$ and $p=2ab$.  These are both squares, so $a^2+b^2=q=c^2$ (!), which defines a triangle with area $\frac{ab}{2}=\frac{2ab}{4}=\frac{p}{4}$, another perfect square.
  • But $c<z$.  This is because $z=q^2+p^2=\left(c^2\right)^2+p^2=c^4+p^2$; unless $p=0$, $c$ is strictly less than $z$ - but $p=0$ doesn't give a triangle, much less a Pythagorean one!   So we have our strictly smaller triangle satisfying the same properties, which leads to an infinite descent, as Fermat called it.

And there is a bonus to all this.  In the proof, we really showed that there is no pair $p$ and $q$ of (coprime) squares such that $q^2-p^2$ is also a perfect square $t^2$; that is what we started with, after all.  So, if $p=u^2$ and $q=v^2$ (forget our previous use of $u$ and $v$), we have that $$v^4-u^4=t^2$$ is impossible.  In your homework, you will use this to prove the famous first case of "Fermat's last theorem": $$x^4+y^4=z^4$$ is not possible for any three positive integers $x,y,z$.

All that remains is your homework.  Remember, do it, even though it's not being handed in Monday!  It is your practice - and preparation for the next class period.

  1. Prove that any line $ax+by=c$ which hits the integer lattice but $gcd(a,b)\neq 1$ is the same as a line $a'x+b'y=c'$ for which $gcd(a',b')=1$, and explain why that means that without loss of generality the first topic doesn't need any more explanations.
  2. Find a primitive Pythagorean triple with at least three digits for each side.
  3. Prove that 360 cannot be the area of a primitive Pythagorean triple triangle.  Is it be the area of some Pythagorean triple triangle?
  4. Find a way to prove that $x^4+y^4=z^4$ is not possible for any three positive integers $x,y,z$.
  5. We already saw that if $x,y,z$ is a primitive Pythagorean triple, then exactly one of $x,y$ is even (divisible by 2).  Prove that $y$ is divisible by 4 and that exactly one of them is divisible by 3. (This proves that every area of a Pythagorean triple triangle is divisible by 6.  It is also true that exactly one of $x,y,z$ is divisible by 5.)
  6. Write down your own definition of a prime number.  Then compare it with the book, a few internet sources, etc.  Should 1 be considered prime?  What about $-1$?  
  7. Search books and/or the Internet and find at least three different proofs that there is no largest prime number.  You don't have to understand all the details; they should be fairly different from each other, though.  Do any of the proofs generate all primes in order?