211Lecture4

pavel@cs.auckland.ac.nz

576(CS Building)

1pm-2pm Tuesday = Office hours

Questions

Example 1

If n, m are odd numbers, then n.m is odd.

Proof

There are Integer numbers K and L such that

n=2K+1, m=2L+1

n.m = (2K+1).(2L+1) = 4KL+2(K+L)+1 - this is an odd number

Example 2

If p,q are rational numbers, then p-q is rational.

Proof

p=n/m, where n,m are Integers and m != 0.

q=l/k where k, and l are Integers and k != 0.

p-q = n/m - l/k = (nk-lm)/mk = this is a rational number.

• Example 1 and Example 2 are examples of direct proofs.

Example 3

If p is rational, and q is an irrational number, then p+q is irrational.

Proof

Assume that p+q is rational. Let l=p+q.

q = t - p is a rational number. By hypothesis, it is Irrational

• This example is done using proof by contradiction. QED

Example 4

If 3/(n^2) then 3/n, where n is an Integer.

Proof

Assume that 3/(n^2)

n = 3k + r, where 0<=r<=3 (r is the remainder) r = 0,1,2

So r can be 1 or 2

1. let r = 1
   1. n^2 = (3k+1)^2 = y*x^2 + b*k+1 hence 3/(n^2)
2. let r = 2
   1. n^2 = (3k+2)^2 = 9k^2 + 12k + 4 =
   2. 3(3k^2 + 4k +1) + 1 thus 3/(n^2) QED

Example 5

sqrt(3) is Irrational

Proof

Assume that sqrt(3) = n/m, where n,m are Integers, m != 0 , and n,m do not have common factors.

Therefore 3 = n/m => 3m^2 = n^2 Then 3/(n^2) => 3/n.

There is k such that n = 3k. 3m^2 = 9k^2 => m^2=3k^2

So 3/m - then 3/m

If sqrt(3) = n/m then 3/n and 3/m n=3n', m=3m'

sqrt(3) = n'/m'