Prove that $\sqrt{3}$ is irrational.

First, let's prove the lemma that if the square of an integer n is divisible by 3, n must be divisible by 3. Why ? A integer can be written in only one of 3 forms:

$$\begin{aligned} Case \space 1: n & = 3x \\ Case \space 2: n & = 3x + 1 \\ Case \space 3: n & = 3x + 2 \\ \end{aligned}$$

where x is an integer. If we take the square of n in each case:

$$\begin{aligned} Case \space 1: n^2 & = (3x)^2 = 9x^2 \\ Case \space 2: n^2 & = (3x + 1)^2 = 9x^2 + 6x + 1 = 3(3x^2 + 2x) + 1 \\ Case \space 3: n^2 & = (3x + 2)^2 = 9x^2 + 12x + 4 = 3(3x^2 + 4x + 1) + 1 \end{aligned}$$

Note that only in case 1 when n is divisible by 3 would $n^2$ be divisible by 3. This completes the proof of the lemma.

Now suppose $\sqrt{3}$ is rational,

$$\exists{p,q \in \mathbb{N}}[\sqrt{3} = \frac{p}{q}]$$

such that p and q has no common factors. Squaring both sides,

$$\begin{aligned} 3 & = \frac{p^2}{q^2} \\ 3q^2 & = p^2 \end{aligned}$$

This means $p^2$ is divisible by 3. By the above lemma, this means p must be divisible by 3. Or p = 3r for some integer r.

$$\begin{aligned} 3q^2 & = p^2 = (3r)^2 = 9r^2 \\ q^2 & = 3r^2 \end{aligned}$$

This means $q^2$ is divisible by 3, and by the lemma above, q must be divisible by 3. To summarize, both p and q are divisible by 3, but this contradicts the initial assumption that p and q has no common factor!

Hence $\sqrt{3}$ is irrational.

# posted by rot13(Unafba Pune) @ 10:49 PM