Mathematics for Computer Science

Chapter 2 The Well Ordering Principle30

LetCbe the set ofcounterexamplesto (*), namely^3

CWWDfnj:::g

Assume for the purpose of obtaining a contradiction thatCis nonempty.

Then by the WOP, there is a smallest number,m 2 C. Thismmust be

positive because....

But ifS.m/holds andmis positive, thenS.m6/orS.m15/must

hold, because....

So supposeS.m6/holds. Then 3 j.m6/, because...

But if 3 j.m6/, then obviously 3 jm, contradicting the fact thatm

is a counterexample.

Next, ifS.m15/holds, we arrive at a contradiction in the same way.

Since we get a contradiction in both cases, we conclude that...

which proves that (*) holds.

Problem 2.3.
Euler’s Conjecturein 1769 was that there are no positive integer solutions to the
equation
a^4 Cb^4 Cc^4 Dd^4 :

Integer values fora;b;c;dthat do satisfy this equation, were first discovered in

1986. So Euler guessed wrong, but it took more two hundred years to prove it.
      Now let’s consider Lehman’s equation, similar to Euler’s but with some coeffi-
      cients:
      8a^4 C4b^4 C2c^4 Dd^4 (2.2)
      Prove that Lehman’s equation (2.2) really does not have any positive integer
      solutions.
      Hint:Consider the minimum value ofaamong all possible solutions to (2.2).

Homework Problems

Problem 2.4.
Use the Well Ordering Principle to prove that any integer greater than or equal to 8
can be represented as the sum of integer multiples of 3 and 5.

(^3) The notation “fnj:::g” means “the set of elements,n, such that... .”