Mathematics for Computer Science

(Frankie) #1

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



  1. 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... .”

Free download pdf