- number patterns,

- proof by mathematical induction,

- divisibility and the division algorithm

- GCD and LCM ( greatest common divisor and least common multiple )

- the Euclidean algorithm

- solving linear Diophantine equations

Unit 1 also contains the proof of the method of mathematical induction. 'The proof of proof by induction'. This post is part 1 of a forthcoming series with an in-depth explanation of this proof. We begin with the concept of proof by contradiction.

#### Proof by contradiction

If finding a direct proof fails we can try proving by contradiction. If we have to prove a proposition P we then assume ~P and show that this assumption implies a contradiction and thus ~P is false or P is true.#### Example

Show that $\sqrt{2}$ is irrational ( can not be expressed as a fraction ).We assume that $\sqrt{2}$ is rational ( not irrational ) and can thus write it as follows: $$\sqrt{2} = \frac{p}{q}$$ where $(p,q)=1$ ( have no common divisors, are relatively prime ).

Then:

$\sqrt{2} = \frac{p}{q} $

$2 = \frac{p^2}{q^2} $

$p^2 = 2q^2 $

So $p^2$ is even. Since the square of an odd number is always odd and the square of an even number is always even, we know that $p$ must be even and can thus be factorized to $2r$.

Then:

$\sqrt{2} = \frac{2r}{q} $

$2 = \frac{4r^2}{q^2} $

$q^2 = 2r^2 $

So q can be factorized further as well to $2s$.

Then:

$(p,q) = (2r,2s) = 2(r,s) > 1$.

This is clearly a contradiction and thus proves that $\sqrt{2}$ must be irrational.

## No comments:

## Post a Comment