Prove that the number [tex]\sqrt{3}[/tex] is irrational.
Solution:
Suppose, on the contrary, that [tex]\sqrt{3}[/tex] is rational. Since [tex]\sqrt{3}\gt 0[/tex], we can write [tex]\sqrt{3}=\frac{p}{q}[/tex], where [tex]p[/tex] and [tex]q[/tex] are natural numbers and the fraction is irreducible ([tex]p[/tex] and [tex]q[/tex] have no common divisor greater than [tex]1[/tex]). Squaring gives
[tex]p^2=3q^2[/tex]
Hence [tex]p^2[/tex] is divisible by [tex]3[/tex]. Then [tex]p[/tex] is also divisible by [tex]3[/tex]. Indeed, otherwise [tex]p=3k+1[/tex] or [tex]p=3k+2[/tex] for some integer [tex]k[/tex], and
[tex](3k+1)^2=3(3k^2+2k)+1,\qquad (3k+2)^2=3(3k^2+4k+1)+1[/tex]
In both cases [tex]p^2[/tex] leaves remainder [tex]1[/tex] when divided by [tex]3[/tex], a contradiction. So [tex]p=3m[/tex] for some natural number [tex]m[/tex], and
[tex]9m^2=3q^2\ \Rightarrow\ q^2=3m^2[/tex]
Hence [tex]q^2[/tex] is divisible by [tex]3[/tex] and, by the same argument, [tex]q[/tex] is divisible by [tex]3[/tex]. Thus [tex]3[/tex] divides both [tex]p[/tex] and [tex]q[/tex], which contradicts the irreducibility of the fraction [tex]\frac{p}{q}[/tex]. Therefore [tex]\sqrt{3}[/tex] is irrational.