Lesson 2-6: Unions and Intersections of Figures (Day 26)

This is what Theoni Pappas writes on page 264 of her Magic of Mathematics:

(nothing)

That's because this is the opening page of Chapter 11, the final chapter of the book, "The Spell of Logic, Recreation, and Games." There is nothing on this page except an illustration. The caption details the fascinating history behind the illustration:

"People have always played games and done puzzles. Books on the origins of various games give numerous examples of ancient games that are still played today. This illustration is from an Egyptian papyrus dating back to 1200 BC. It is a humorous rendition of a goat and a lion playing the game of senet. Senet was one of the most popular games of its time, and was played by all sectors of society. Unfortunately, there is no remaining documentation on exactly how it was played, but a possible version of senet has been devised using the findings and work of archaeologists.

Today is Rosh Hashanah, the Jewish New Year. It is also the Islamic New Year -- this being the second of three straight years when the two new years coincide. The Jewish Calendar is lunisolar while the Islamic Calendar is purely lunar.

Rosh Hashanah is significant for teachers and students only in that the LAUSD observes the two High Holidays, and so schools are closed today. Last year, my old charter school closed for Rosh Hashanah when it was co-located with two LAUSD elementary schools. But now that it has its own campuses, I'm not sure whether it observes the LAUSD holidays Admissions Day or Rosh Hashanah.

The holiday falls on Thursday this year. Some people wish that it would be tomorrow instead of today so that there could be a three-day weekend. But neither Rosh Hashanah nor Yom Kippur can ever fall on Friday (or Sunday). Recall that these holidays were created for the Jews -- not schools, teachers, or students -- and having these holidays fall on the day before or after Saturday (the Sabbath) would be inconvenient for Jews.

If today were a holiday at my old school, it might have been better for the annual trip to the LA County Fair to be tomorrow -- if having school on Friday after a Thursday holiday is so inconvenient we might as well make it a field trip day. But I know for a fact that the fair trip was two weeks ago -- so maybe that means that today isn't a holiday at my old school after all.

Meanwhile, Yom Kippur falls on the Sabbath itself this year. Of course, all schools are closed that day -- and there is no "observed" holiday on Friday or any other day (as there will be when Veteran's Day falls on a Saturday this year). This means that the two LAUSD schools formerly co-located with my old charter, the last day of school will be on a Thursday (as opposed to a Friday last year). All of this is irrelevant to me now, of course, since I'm subbing in a different district that doesn't observe Jewish holidays at all.

Chapter 6 of Stanley Ogilvy's Excursions in Number Theory is called "Diophantine Equations." The chapter begins:

"Diophantus of Alexandria (dates unknown, circa 3rd century of the Christian era) concerned himself with solutions in integers of certain simple algebraic equations. The name Diophantine still attaches to equations for which one wants only integers as solutions."

And Ogilvy begins with one of the best-known Diophantine equations, the Pythagorean Theorem:

x^2 + y^2 = z^2

with its simplest solution:

3^2 + 4^2 = 5^2

This equation has infinitely many solutions, with (6, 8, 10) being one of them. Ogilvy points out that this solution isn't that much different from (3, 4, 5) -- in fact, viewed as right triangles, the 3-4-5 and 6-8-10 triangles are similar. Our first task today is to find more primitive Pythagorean triples -- those which can't be reduced to a smaller solution.

The author tells us that x and y can't both be even, since z would also be even and then we'd be able to divide by 2, just like 6-8-10. He adds that x and y can't both be odd either, and he uses congruence mod 4 to tell us why. Odd numbers are == to either 1 or -1 mod 4, and so all odd squares must be == to 1 mod 4. The sum of two odd squares is thus == 2 mod 4, yet all even squares are == 0 mod 4.

So one of x and y is odd and the other is even. Without loss of generality, we let x be odd and y be even -- and since y is even, we let y = 2u for some u:

x^2 + 4u^2 = z^2
4u^2 = z^2 - x^2
         = (z + x)(z - x)

Since both x and z are odd, z + x and z - x are both even. So we substitute:

z + x = 2s
z - x = 2r
4u^2 = 2s2r
u^2 = rs

Notice that the equations for z + x and z - x are set up perfectly as a system of equations that can be solved using the elimination method: z = r + s and x = r - s are the solutions.

Now we focus on the equation u^2 = rs. We notice that the GCD of r and s must be the same as the GCD of their sum z and their difference x. But the GCD of z and x is 1, since otherwise we could divide the common factor out and we wouldn't have a primitive solution. But their product, u^2, can only be a square if both r and s are squares -- otherwise their GCD wouldn't be 1. We let r = m^2 for some m, and s = n^2 for some n. We now write the original triple in terms of m and n:

x = m^2 - n^2
y = 2mn
z = m^2 + n^2

Ogilvy tells us that as long as m > n (to keep x positive), m and n are relatively prime, and one of them is even with the other odd, then this generates a primitive Pythagorean triple. He provides us with three examples:

(1) m = 3, n = 2
x = 9 - 4 = 5
y = 2 * 3 * 2 = 12
z = 9 + 4 = 13 (Primitive)

(2) m = 4, n = 2
x = 16 - 4 = 12
y = 2 * 4 * 2 = 16
z = 16 + 4 = 20 (Nonprimitive; multiple of 3-4-5 by the square number 4)

(3) m = 5, n = 3
x = 25 - 9 = 16
y = 2 * 5 * 3 = 30
z = 25 + 9 = 34 (Nonprimitive; multiple of 8-15-17 by 2)

Ogilvy now performs a few tricks with these triples. First, he proves a theorem:

The length of the radius of the circle inscribed in a Pythagorean triangle is always an integer.

To prove this, he lets ABC be the triangle with the right angle at C. Again x, y, and z are the sides of the triangle, so the area is xy/2. Now he lets O be the incenter of the circle with r the inradius, and finds the area of ABC by adding the areas of BOC, COA, and AOB:

xy/2 = rx/2 + ry/2 + rz/2
       = r(x + y + z)/2
r = xy/(x + y + z)

We now substitute the values of x, y, and z in terms of m and n:

r = (m^2 - n^2)2mn / (m^2 - n^2 + 2mn + m^2 + n^2) = n(m - n).

Not only have we proved that r is an integer, but we have also found which integer it is. For the basic 3-4-5 triangle, m = 2 and n = 1, so the inradius is 1. Ogilvy describes this as "something, possibly, that you never knew before?" Actually, I've seen questions of this type on the Pappas calendar -- but at least now I can use Ogilvy's trick to find the inradius.

The author now asks one more question before leaving Pythagorean triples:

"How many non-collinear points in a plane can be spaced at integral distances each from each?"

He tells us that if the points are collinear, the answer is trivial -- infinitely many, just by placing the points at integer coordinates. For the non-linear case, the answer is finitely but arbitrarily many. In his example, he places one point on the y-axis and all the others on the x-axis.

To find a solution, we start with some Pythagorean triples. Ogilvy decides to let n be 1, 2, 3, 4, 5, and then he lets m = n + 1. This generates the triples 3-4-5, 5-12-13, 7-24-25, 9-40-41, and 11-60-61. We then multiply all the short legs together -- 3 * 5 * 7 * 9 * 11 = 10395. This is the coordinate of the lone point we place on the y-axis -- (0, 10395).

Now we must find points to place on the x-axis. We take the product 3 * 5 * 7 * 9 * 11 again, but this time we replace each factor, one at a time, with the length of the long leg in the corresponding triple:

x_1 = 4 * 5 * 7 * 9 * 11
x_2 = 3 * 12 * 7 * 9 * 11
x_3 = 3 * 5 * 24 * 9 * 11
x_4 = 3 * 5 * 7 * 40 * 11
x_5 = 3 * 5 * 7 * 9 * 60

We then see that if we then replace these factors by the hypotenuse in the corresponding triangle, we then obtain the distance between each x-point and the y-point, which is an integer. So we have five different overlapping Pythagorean triangles, all scaled up so that they have a short leg in common.

At this point, Ogilvy moves from the Pythagorean Theorem:

x^2 + y^2 = z^2

to possibly the world's most famous Diophantine equation:

x^n + y^n = z ^n

Ogilvy tells us that this is called Fermat's Last Theorem, except maybe "Fermat's Conjecture" was a better name for it since we have only "marginal" evidence that Fermat ever had a proof. Of course, this was back at the time Ogilvy published his book. Since then, Fermat's Last Theorem was proved by the British mathematician Andrew Wiles. Actually, Wiles first published his proof around the time that Pappas wrote her book -- she tells us on pages 163-164 that his proof was still being verified. (I never covered pages 163-164 on the blog -- the 163rd and 164th days of the calendar year were just after the last day of school, during a stretch when I didn't post.)

But Fermat himself proved the simplest case, n = 4. In fact, not only can the sum of two fourth powers never be a fourth power, it can't even be a square. This stronger statement is equation (1):

(1) x^4 + y^4 = z^2.

We reconstruct Fermat's proof, which is proved using "infinite descent" -- which I describe as where indirect proof meets proof by induction. Assume that we have a primitive solution (x, y, z):

(x^2)^2 + (y^2)^2 = z^2

So x^2, y^2, z are a Pythagorean triple. Without loss of generality, let y^2 be even, and we can write this in terms of m and n from before:

x^2 = m^2 - n^2
y^2 = 2mn
z = m^2 + n^2

Now m must be odd and n even, since if it were the other way around:

x^2 == 0 - 1 (mod 4) == 3 (mod 4)

yet no square is == 3 mod 4. So we let n = 2k for some k:

y^2 = 2m * 2k

Since m and k are relatively prime (as m and n are) and their product is a square, they must each be squares themselves:

m = r^2, k = s^2, y = 2rs,
x^2 = r^4 - 4s^4, x^2 + 4s^4 = r^4

So now we have another Pythagorean triple, namely x, 2s^2, and r^2. So we use the m-n trick again:

x = p^2 - q^2
2s^2 = 2pq
r^2 = p^2 + q^2

We now do the "squares trick" again -- since pq = s^2, p = a^2 and q = b^2 for some a, b:

(2) r^2 = a^4 + b^4

which we compare to equation (1):

(1) z^2 = x^4 + y^4

This is the original equation that we're trying to solve! So if (x, y, z) is a solution then so is (a, b, r) -- but this isn't any ordinary solution:

z = m^2 + n^2 = r^4 + 4s^4

So z is much, much greater than r. In order words, for any solution there exists a smaller solution -- but this is problematic, because we could keep finding smaller solutions forever by repeating the above process over and over:

r > r_1 > r_2 > ... > 0

This is why we call it "infinite descent" -- it's a contradiction because there is no infinitely descending chain of natural numbers. Therefore:

x^4 + y^4 = z^4

has no solution. QED FLT n = 4.

Now Ogilvy plays around with Fermat's Last Theorem. For example, one case already proved by the time of his book is the n = 3 case:

x^3 + y^3 = z^3

For this to have no positive integer solution is to say that:

x^3 + y^3 = 1

has no rational solutions other than (1, 0) and (0, 1). Ogilvy shows us the graph of this equation, which looks like a slanted bell curve. (It's easy to graph on a TI in the form y = cbrt(1 - x^3).) FLT tells us that even though the rationals are dense in the reals, this graph manages to avoid all except two rational points. This is strange, until the author reminds us that:

x^2 + y^2 = pi^2

a circle of radius pi also avoids all rational points due to the transcendence of pi.

Ogilvy now shows us some other Diophantine equations. Even two cubes can't add up to a cube, three cubes can:

x^2 + y^2 + z^3 = w^3 -> 3^3 + 4^3 + 5^3 = 6^3

Also, five cubes can add up to a cube:

1^3 + 3^3 + 4^3 + 5^3 + 8^3 = 9^3

But it's probably impossible for the first k n'th powers to add up to the next n'th power:

1^n + 2^n + 3^n + ... + k^n = (k + 1)^n

Except for 1 + 2 = 3, this has no solution with a million digits or less.

The following equation:

1^2 + 2^2 + 3^2 + ... + k^2 = N^2

has only one nontrivial solution -- k = 24, N = 70. It's called the "cannonball problem," and it tells us that the only way to stack a square number of cannonballs in a square pyramid is to stack 4900 of them in 24 rows.

Now Ogilvy moves on to another Diophantine equation:

y^2 + 2 = x^3

It's only solutions are (3, 5) and (3, -5) -- that is, the only cube two more than a square is 27. Ogilvy now gives the proof, but this proof isn't completed in the integers. First, he reminds us that:

(x^a)^b = (x^b)^a

isn't always true. Here is a counterexample:

((-2)^(1/2))^2 = sqrt(-2)^2 = -2
((-2)^2)^(1/2) = sqrt(4) = 2

Also, sqrt(a)sqrt(b) isn't always sqrt(ab):

sqrt(-9)sqrt(-4) = 3i * 2i = 6i^2 = -6
sqrt(-9 * -4) = sqrt(36) = 6

Now we begin the proof that:

y^2 + 2 = x^3

has only one positive integer solution. We begin by factoring the left side:

(y + sqrt(-2))(y - sqrt(-2)) = y^2 + 2.

At this point, Ogilvy points out that we can't factor y^2 + 2 in the integers, but we're able to factor it in another set -- the ring Z[sqrt(-2)]. Do you remember the big discussion about how in the Common Core standards the set of polynomials is "a set analogous to the integers"? Well, Z[sqrt(-2)] is another set analogous to the integers -- a set called a "ring." And just like the integers, the ring Z[sqrt(-2)] has unique factorization.

According to Ogilvy, it's also possible to prove that y + sqrt(-2) and y - sqrt(-2) are relatively prime in the ring Z[sqrt(-2)]. In our proof of FLT n = 4, we repeatedly used the fact that if the product of two relatively prime numbers is a square then each is itself a square (the "squares trick"). Well, since the product is also equal to x^3, we can use the cubes trick to prove that y + sqrt(-2) and y - sqrt(-2) must be cubes in Z[sqrt(-2)]:

y + sqrt(-2) = (u + v sqrt(-2))^3
                   = u^3 + 3u^2 v sqrt(-2) - 6uv^2 - 2v^3 sqrt(-2).

Equating the imaginary parts:

1 = 3u^2 v - 2v^3 = v(3u^2 - 2v^2)

The only solutions are v = 1 and u = 1 or -1. Then we equate the real parts to obtain y = -5 or 5. QED

Ogilvy warns us that we can't take unique factorization for granted. The ring Z[sqrt(-2)] has unique factorization, but Z[sqrt(-5)] doesn't:

6 = 2 * 3 = (1 + sqrt(-5))(1 - sqrt(-5))

The author tells us how similar-looking equations can have no solution or many solutions:

y^2 - 7 = x^3 has no solutions:
y^2 - 17 = x^3 has eight solutions (x = -2, -1, 2, 4, 8, 43, 52, and 5234, with x^3 = 143,384,152,9040

For the next problem, the solution was unknown to Ogilvy:

a^b - c^d = 1 (all variables different, b and d greater than 1)

The only solution is a = d = 3, b = c = 2. This was proved in 2002, well after Ogilvy's book, by the Romanian mathematician Preda Mihailescu.

Ogilvy gives us a list of Diophantine problems posed by the Polish mathematician Waclaw Sierpinksi (yes, of fractal triangle fame), a few years before Ogilvy's book. The first is:

(x + y + z)^3 = xyz

Here are the others?

1. n^n + 1 a prime? (other than n = 1, 2, 4)
2. n! + 1 a square? (other than n = 4, 5, 7)
3. x^3 + y^3 + z^3 = 3 (other than (1, 1, 1), (4, 4, -5) in any order)
4. x^3 + y^3 + z^3 = 30
5. x^3 + y^3 + 2z^3 = n has solutions for all n? (76 and 99 are unknown)
6. Goldbach's conjecture (weak form proved a few years ago as mentioned on blog)
7. Twin primes conjecture

Ogilvy also warns us that just because we have:

(a + b)^2 = a^2 + 2ab + b^2

it doesn't mean that a^2 + 3ab + b^2 can't be a square. Try a = 7, b = 3. This actually shows up in a counterexample to the conjecture "the product of four consecutive terms of an arithmetic sequence is always a square but never a fourth power":

a(a + b)(a + 2b)(a + 3b) + b^4 factors as (a^2 + 3ab + b^2)^2.

So a = 7, b = 3 makes the sum a fourth power. The sequence is 7, 10, 13, 16 and the sum is 11^4.

Here is the final problem in this chapter: A farmer sells p/q of his eggs plus p/q of an egg to his first customer, p/q of his eggs of p/q of an egg to his second customer, and so on until all the eggs have been sold to n customers. Ogilvy gives the answer as:

p = q - 1, starting number of eggs = q^n - 1

and he hints:

"In case total frustration sets in, there is a reference in the Notes."

But I don't need to look at his notes -- it appears that number bases will help us again! Try looking at the problem in base q -- then p, being q - 1, is the omega.

Today's chapter was all about sets of solutions to Diophantine equations -- sometimes the solution set is empty, other times it's infinite. Sets also appear in today's U of Chicago lesson.

Lesson 2-6 of the U of Chicago text is called "Unions and Intersections of Figures." (It appears as Lesson 2-5 in the modern edition of the text.)

This is what I wrote two years ago about today's lesson:

Lesson 2-6 of the U of Chicago text focuses on unions and intersections. This is, of course, the domain of set theory.

In many ways, set theory is the basis of modern mathematics, and so many textbooks -- including higher math such as Precalculus and beyond -- mention set theory early on. Of course, the focus in this text is on unions and intersections of geometric figures. In particular, unions are used to define both polygon and angle, while intersections are used to define parallel lines.

The first three examples in the text, where the underlying sets contain natural numbers, real numbers, and points -- are OK. But I didn't like the fourth example, on airlines. I've decided to throw this one out -- if we want a non-mathematical example, why not just use sets of letters, such as {a, e, i, o, u}, the set of vowels?

One of the most important sets in mathematics is the null set, or empty set. According to the text, this set can be written as either { } or an O with a line through it (often called O-slash by students). Once again, since I can't represent that symbol on Blogger, let's use the strikethrough instead: O.

Now the text mentions that the intersection of two sets might be the empty set. But it doesn't mention what happens when one finds the union, or intersection, of the empty set and another set. As it turns out, the union of the empty set and another set is that other set -- so the empty set acts as the identity element for union, just as 0 is the identity for addition and 1 is the multiplicative identity. But the intersection of the empty set and another set is the empty set -- so the empty set acts as the absorbing element for intersection, just as 0 is the absorbing element for multiplication.

One question students often ask is, if { } is the empty set and O is the empty set, what's {O}? When I was young, I once heard a teacher point out that this is not the empty set because it's no longer empty -- it contains an element.