Prove sqrt2 is an irrational number

1. Traditional method using contradiction

Assume sqrt2 is a rational number, so that sqrt2 = a/b, a and b are relatively prime integers.

sqrt2 = a/b => 2 =a²/b² => 2b² = a²
so that a² is an even number, then a is an even number as well.
Therefore, we can let a = 2c => 2b² =2(2C)² => b² = 4c²
so that b² is an even number, then b is an even number as well.
Now both a and b are even number, they cannot be relatively prime, which is contrary to assumption: sqrt2 is a rational number, so that sqrt2 = a/b, a and b are relatively prime integers.

Therefore assumption is false, and sqrt2 is an irrational number.

2. Prove using strong induction

P(n) is the statement that sqrt2 =/= n/b for any positive integer b.

Basic step:

Prove P(1) is true

P(1) : 1/b <=1 <sqrt2, so that sqrt2 =/= 1/b, P(1) is true.

Inductive step:

We assume P(j) is true for all 1<=j<=k: sqrt2 =/= j/b, and we need prove P(k+1) is true as well: sqrt2 =/= (k+1)/b

We assume sqrt2 = (k+1)/b for some b. So that 2 = (k+1)²/b² => 2b² = (k+1)²
we can conclude that (k+1)² is an even number and k+1 is an even number as well.

Let k+1 = 2c, 2b² = (k+1)² => 2b² = (2c)² => b² = 2c²
we can conclude that b is an even number.

Let b = 2d, sqrt2 = (k+1)/b => sqrt2 = 2c/2d = c/d.
For sqrt2 = c/d, d is a positive integer, c<k for k>1 (since k+1 = 2c), this contradicts our previous assumption: We assume P(j) is true for all 1<=j<=k: sqrt2 =/= j/b.

Therefore our second assumption: We assume sqrt2 = (k+1)/b for some b. is false. We conclude sqrt2 =/= (k+1)/b for all positive integer b.

So that sqrt2 =/= n/b for any positive integer b, and sqrt2 is an irrational number.

2018/12/02