<s>[INST] Prove that the square root of 3 is irrational I'm trying to do this proof by contradiction. I know I have to use a lemma to establish that if $x$ is divisible by $3$, then $x^2$ is divisible by $3$. The lemma is the easy part. Any thoughts? How should I extend the proof for this to the square root of $6$?
 [/INST] suppose $\sqrt{3}$ is rational, then $\sqrt{3}=\frac{a}{b} $ for some $(a,b)
$
suppose we have $a/b$ in simplest form.
\begin{align}
\sqrt{3}&=\frac{a}{b}\\
a^2&=3b^2
\end{align}
if $b$ is even, then a is also even in which case $a/b$ is not in simplest form.
if $b$ is odd then $a$ is also odd.
Therefore:
\begin{align}
a&=2n+1\\
b&=2m+1\\
(2n+1)^2&=3(2m+1)^2\\
4n^2+4n+1&=12m^2+12m+3\\
4n^2+4n&=12m^2+12m+2\\
2n^2+2n&=6m^2+6m+1\\
2(n^2+n)&=2(3m^2+3m)+1
\end{align}
Since $(n^2+n)$ is an integer, the left hand side is even. Since $(3m^2+3m)$ is an integer, the right hand side is odd and we have found a contradiction, therefore our hypothesis is false.
</s>