Description

4. In class we talked about the Four Color Theorem: if X is a planar graph with a finite number of

vertices, then X can be colored using only 4 colors R, B, G and Y . In other words, each vertex of

the graph can be assigned R, B, G or Y so that when two vertices are joined by an edge, those two

vertices must have different colors. Take a look at the graphs on the next page. (a) Find a coloring of the graph labeled A that uses 4 colors. Also, explain why no fewer colors will

work. (b) Explain why the graph labeled B cannot be colored with 4 colors. This graph is, however, not

planar. Explain why it does not violate the Four Color Theorem. It might be helpful to think

about the truth table of P =⇒ Q. 5. In class we talked about Fermat’s Last Theorem. In this problem, we show that

x

2 + y

2 = z

2

has an infinite number of positive integer solutions (x, y, z) where (x, y, z) have no common factors.

We already know about the solutions (3, 4, 5) and (5, 12, 13) and perhaps (8, 15, 17) since they show up

all the time in high school. We call a solution (x, y, z) to the equation a primitive Pythagorean triple

when (x, y, z) have no common factors.(a) Let a and b be two positive integers with a > b. Show that setting x = a

2 − b

2

, y = 2ab, and

z = a

2 + b

2 give a solution to the equation x

2 + y

2 = z

2

. (b) What values of a and b yield the three Pythagorean triples above? (c) Try your best to argue that if a and b have a common prime factor p, then x, y, and z will all

have p as a factor.

(d) What common factor will x, y, z share if a and b have the same parity, meaning they are both

even or both odd? (e) In fact, if we avoid the two situations above, then (x, y, z) will be primitive. Use this result to

find an infinite number of primitive Pythagorean triples. (f) (Bonus) In fact, every primitive Pythagorean triple is obtained by this method. The first step in

proving this is to see that for any primitive solution (x, y, z), exactly one of x and y must be even.

In particular, x and y cannot both be odd. In class (and in the book in Example 1.21), we saw

that if x is odd, then x

2 − 1 is divisible by 8, or equivalently, x

2

is of the form 8k + 1 for some

integer k. Use this result (a theorem) to show that if x and y are both odd, then x

2 + y

2

is even,

but never divisible by 4. On the other hand, if z

2 = x

2 + y

2 and x and y are both odd, explain

why z

2

is divisible by 4. Complete the proof that if x

2 + y

2 = z

2

, then x and y cannot both be

odd.

Tags:

positive integers

Pythagorean

Four Color Theorem

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.